도로 뒤집기

당신은 일방통행 시의 시청에서 일한다. 이 도시는 관내 모든 도로를 한 방향으로만 통행하도록 규정한다. 당신은 새 택지지구와 그 도로망에 대한 제안서를 평가하고 있다. 초기 제안서 일부에서 관찰된 문제는, 제안된 도로를 따라 어떤 위치에서 다른 위치로 갈 수 없는 경우가 있다는 것이다. 이후 제안서의 평가를 빠르게 하기 위해, 임의의 위치에서 다른 임의의 위치로 갈 수 있는지 판별하는 프로그램을 작성하려고 한다. 이런 제안서를 유효하다고 부른다. 그리고 제안서가 유효하지 않다면, 도로 하나의 방향을 뒤집어 고칠 수 있는 쉬운 방법이 있는지 프로그램이 알아내야 한다.

각 테스트 케이스는 두 정수 1 ≤ m ≤ 50과 0 ≤ n ≤ m(m − 1)/2가 있는 줄로 시작한다. m은 제안서에 있는 위치의 수이고, n은 이 위치들을 잇는 도로의 수이다. 이어서 n개의 줄이 주어진다. 각 줄에는 공백으로 구분된 두 정수 a와 b가 있고, 0 ≤ a, b < m이며 a ≠ b이다. 이는 위치 a에서 위치 b로 가는 도로가 있음을 뜻한다. a에서 b로 가는 도로가 있으면 b에서 a로 가는 도로는 없다. 또한 두 위치 사이에 도로가 두 개 이상 있는 경우는 없다.

각 케이스마다 케이스 번호를 출력하고, 그 뒤에 제안서가 유효한지 아닌지를 나타내는 표시를 출력한다. 제안서가 유효하면 valid를 출력한다. 유효하지 않지만 도로 하나의 방향을 뒤집어 유효하게 만들 수 있으면, 뒤집어야 할 기존 도로를 나타내는 두 위치를 출력한다. 도로를 뒤집어 유효한 제안서를 만들 수 있는 방법이 여러 개면, 입력에 가장 먼저 나타나는 것을 출력한다. 제안서가 유효하지 않고 도로 하나를 뒤집어서 유효하게 만들 수 없으면 invalid를 출력한다. 출력 형식은 샘플 출력을 따른다.