#abc209d. [abc209_d]Collision
[abc209_d]Collision
Problem Statement
The Kingdom of Takahashi is made up of towns and roads, where the towns are numbered through . The -th road connects Town and Town , so that you can get from every town to every town by using some roads. All the roads have the same length.
You will be given queries. In the -th query , given integers and , solve the following problem:
- Takahashi is now at Town and Aoki is now at Town . They will leave the towns simultaneously and start traveling at the same speed, Takahashi heading to Town and Aoki heading to Town . Determine whether they will meet at a town or halfway along a road. Here, assume that both of them travel along the shortest paths, and the time it takes to pass towns is negligible.
Constraints
- All values in input are integers.
- It is possible to get from every town to every town by using some roads.
Input
Input is given from Standard Input in the following format:
Output
Print lines. The -th line should contain Town
if Takahashi and Aoki will meet at a town in the -th query, and Road
if they meet halfway along a road in that query.
Sample Input 1
4 1
1 2
2 3
2 4
1 2
Sample Output 1
Road
In the first and only query, Takahashi and Aoki simultaneously leave Town and Town , respectively, and they will meet halfway along the -st road, so we should print Road
.
Sample Input 2
5 2
1 2
2 3
3 4
4 5
1 3
1 5
Sample Output 2
Town
Town
In the first query, Takahashi and Aoki simultaneously leave Town and Town , respectively, and they will meet at Town , so we should print Town
.
In the first query, Takahashi and Aoki simultaneously leave Town and Town , respectively, and they will meet at Town , so we should print Town
.
Sample Input 3
9 9
2 3
5 6
4 8
8 9
4 5
3 4
1 9
3 7
7 9
2 5
2 6
4 6
2 4
5 8
7 8
3 6
5 6
Sample Output 3
Town
Road
Town
Town
Town
Town
Road
Road
Road