Chess Championship Distant Sites

The International Chess Championship organizing committee has decided that the site for the Championship has to be chosen in such way that its distance from the capital city of the country is maximized. The reason is obvious, the committe wants to isolate the competitors and the visitors from the tempations of the capital so that they all stay on the Championship site as long as possible.
The site should consist of three towns each of which is connected to directly the other two by a road. Two towns are connected directly by a road R if there is no other town on R between A and B. The distance between two towns A and B is the minimum number of pairs of directly connected towns on the way from A to B. The distance of any possible site from the capital city is equal to the sum of the distances from each of the three towns representing the site to the capital city.
To get better understanding of the task you might also want to read the previous problem related to the Campionship committee decisions.

     

Image 1. Town connection schemes depicting input data in Examples bellow. The capital cities are highlighted. In case a), there are two most distant sites from the capital in node 9, the sites are {0, 1, 3} and {2, 3, 5} and their distance from the capital is 10. In case b), there are 16 possible sites in the whole country and all share the same distance 5 from the capital in node 9. In case c), there is only one most distant site from the capital in node 3, the site is {8, 9, 10} and its distance from the capital is 6.

The task

You are given the scheme of road connections between the towns in the country. Find all championship sites which distance from the capital city is maximum possible.


Input

The first input line contains three integers N, M, C separated by space. The values indicate (in this order) the number of towns in the country, the number of pairs of neigbour towns and the label of the capital city. The towns are labeled by integers 0, 1, ..., N−1. Next, there are M text lines, each describe one pair of neighbour towns. The line contains the labels of the towns separated by space. The order of towns in the pair and the order of pairs of towns in the input is arbitrary.
It holds, 1 ≤ N ≤ 5000, 1 ≤ M ≤ 40 000.
You may assume that each town in the country is connected to the capital city by at least one sequence of roads.

Output

The output contains one text line with two integers D and S separated by space. D is equal to the maximum possible distance of a championship site from the capital city, S is the number of all sites which are located at distance D from the capital city.

Example 1

Input
10 17 9
0 1
0 3
1 3
1 4
2 3
3 4
2 5
3 5
3 6
4 6
4 7
5 6
6 7
6 8
7 8
7 9
8 9
Output
10 2
The data of Example 1 are depicted in Image 1a).

Example 2

Input
10 25 9
0 7
0 6
0 5
0 4
1 7
1 6
1 5
1 4
2 7
2 6
2 5
2 4
3 7
3 6
3 5
3 4
0 8
1 8
2 8
3 8
4 8
5 8
6 8
7 8
9 8
Output
5 16
The data of Example 2 are depicted in Image 1b).

Example 3

Input
11 16 3
0 1
0 2
1 2
1 3
2 3
3 4
4 5
5 6
4 6
3 7
7 8
7 9
7 10
8 9
8 10 
9 10
Output
6 1
The data of Example 3 are depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set