Reversing Roads

You work for the city of One-Direction-Ville. The city mandates that every road in its limits be one direction only. You are evaluating proposals for a new subdivision and its road network. One problem youve observed in some early proposals is that it is impossible to get to certain locations from others along the proposed roads. In order to speed up evaluation of subsequent proposals, you want to write a program to determine if it is possible to get to any location from any other location; you call this a valid proposal. And if a proposal is not valid, then your program should find out if there is an easy way to fix it by reversing the direction of one of the roads.

Input

Input consists of several test cases, at most 55. Each test case begins with a line containing two integers, 1m501m50 and 0nm(m1)/20nm(m1)/2. mm indicates the number of locations in the proposal, and nn indicates the number of roads connecting these locations. Following this are nn lines. Each line contains two space-separated integers aa and bb, where 0a,bno road from bb to aa. Also, there will never be more than one road between two locations.

The last test case is followed by end-of-file.

Output

For each case, display the case number followed by an indication of whether the proposal is valid or not. If the proposal is valid, output valid. If it is not valid, but by reversing the direction of one roads it can become valid, print the two locations which describe the existing road that should be reversed. If more than one road reversal can create a valid proposal, print the first one that appears in the input. If the proposal is not valid and impossible to become valid by reversing one road, print invalid. Follow the format of the sample output.

Sample Input 1	Sample Output 1
3 3 0 1 1 2 2 0 3 3 0 1 1 2 0 2 3 2 1 2 0 2 4 4 0 1 1 2 2 3 0 3	Case 1: valid Case 2: 0 2 Case 3: invalid Case 4: 0 3