Luke has a treasure map. The treasure map has N cities (Numbered 1 to N).

These cities are connected with some paths. And there is a treasure in every city.

So if Luke arrives a city, he can get the treasure in the city.

There are multiple test cases.
Each case starts with three integers N ,M S (1<=N<=100000 ,0<=M<=150000), means the number of cities and the paths. S means the start city of Luke.
And next are M pairs of integers Vi and Ui(1<=Vi,Ui<=N), means there is a path from Vi to Ui(one-way path).

For each test case, print a line “Case T:”,T starts with 1. The next line print the maximum of treasures.