I :: Wonder Island

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Ebrahim interested in traveling around the world. He usually prefers going on road trips with his friends. This time he decided to become familiar by the peoples in different provinces of the Wonder Island. So, when he enter a city of a province he try to leave the province as soon as possible in order to see more provinces and become familiar with more cultures. This Island is named Wonder because of its road map structure between the cities of each province. Two cities A and B belong to a same province if and only if we can have a road trip from A to B and also from B to A.

Tourist manager of Wonder Island wants to plan a satisfactory trip for Ebrahim. Unfortunately, there is not any road path between Ebrahim’s country and the Wonder Island, but there is a direct flight between his country and all the cities of the Wonder Island in both directions. Help the tourist manager of the country to plan a trip for Ebrahim so that he can visit maximum number of provinces as soon as possible. 

Because of some military restrictions, Ebrahim can not leave his country more than once. Therefore, in the trip plan you can consider only two flights; one for traveling  to Wonder Island and the other to return back home.

Input

The first line of the input contains an integer T<=100 denoting the number of test-cases. Each test-case begins with two integers 1<=N<=1,000 and 0<=M<=N*(N+1)/2, denoting the number of cities and the number of directed roads in Wonder Island. The next N lines each contain two not equal numbers 1<=A,B<=N, referring to a direct road from city A to city B. It is guaranteed that all the roads are distinct. 

Output

For each test-case, output in a single line the number of provinces and the number of cities that Ebrahim will visit during his trip to Wonder Island.

Sample Input

2
4 5
3 2
2 4
1 4
2 3
1 3
5 5
5 4
2 4
4 3
2 1
3 2

Sample Output

3 4
3 5

Submit

Source: 13th Iran Nationwide Internet Contest - Shiraz