파이프 하이프
시간 제한3초메모리 제한512 MB
게이트 n개와 파이프 m개가 있는 장치를 t번 이어 붙였을 때, 그와 동일한 동작을 하는 단일 장치의 파이프 목록을 출력합니다.
문제
누구나 알고 있듯이 Flubbyplaxmol은 놀라운 에너지 특성을 지닌 끈적한 유체이며, 가까운 미래에 인류의 우주선이 태양계 밖으로 나아가 새로운 Goldilocks 행성에 정착하는 항해의 동력이 될 수도 있다. 여러분의 친구는 Terrifically Powerful Transports Laboratories(줄여서 TPT Labs)에서 Flubbyendoslasher를 연구하고 있다. Flubbyendoslasher는 n개의 입구 게이트와 n개의 출구 게이트 사이에서 Flubbyplaxmol을 보내는 비교적 단순한 장치다. Flubbyendoslasher에서 Flubbyplaxmol은 서로 다른 입구 게이트로 들어온다. 파이프를 따라 흐른 뒤 최종적으로 출구 게이트 0개, 1개, 또는 여러 개로 나간다. Flubbyplaxmol은 잘 섞이지 않으므로, Flubbyendoslasher 안의 흐름은 서로 섞이지 않는다. 특히 서로 다른 두 입구 게이트가 같은 출구 게이트에 연결되는 경우는 없다.
친구는 t-folded Flubbyendoslasher, 줄여서 t-fF를 전문으로 연구한다. t-fF는 동일한 Flubbyendoslasher t개를 여러 층으로 쌓은 구조이며, t는 매우 클 수 있다. t-fF에서 j번째 Flubbyendoslasher의 i번째 출구 게이트로 나온 Flubbyplaxmol은 곧바로 (j + 1)번째 Flubbyendoslasher의 i번째 입구 게이트로 들어간다. 출구 게이트 중에는 입구 게이트와 연결되지 않는 것도 있고, 그 반대도 있다. 이 경우 해당 게이트로는 Flubbyplaxmol이 들어오거나 나가지 않는다.
그림 2: 2-folded Flubbyendoslasher의 모습.
친구는 t-fF가 항상 하나의 Flubbyendoslasher와 동일하다는 사실을 발견했다. 이 결과를 이용하면 배관을 크게 최적화할 수 있다. 이를 실제로 활용하려면 여러분의 도움이 필요하다. 정수 t와 t-fF를 만드는 데 쓰인 초기 Flubbyendoslasher의 설명이 주어진다. 목표는 그 t-fF와 동일한 Flubbyendoslasher의 설명을 구하는 것이다.
그림 3: 그림 2의 2-fF와 동일한 Flubbyendoslasher.
입력
입력 파일에는 여러 개의 테스트 케이스가 들어 있다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 있다. 이어서 각 테스트 케이스가 나온다. 테스트 케이스의 첫 줄에는 공백으로 구분된 정수 n, m, t가 있다.
- 은 Flubbyendoslasher의 게이트 수이다.
- 은 Flubbyendoslasher에서 입구 게이트와 출구 게이트를 잇는 파이프의 수이다.
- 은 folded Flubbyendoslasher에서 쌓인 Flubbyendoslasher의 복사본 수이다.
나머지 m줄은 파이프를 설명한다. i번째 줄에는 공백으로 구분된 정수 a_i와 b_i가 있다. 입구 게이트 에 들어간 Flubbyplaxmol이 출구 게이트 까지 흐른다는 뜻이다. 파이프는 임의의 순서로 주어진다. 같은 입구 게이트가 여러 번 나타날 수 있지만, 각 출구 게이트는 최대 한 번만 나타난다.
출력
각 테스트 케이스에 대해, t-folded Flubbyendoslasher와 동일한 Flubbyendoslasher의 설명을 출력한다. 첫 줄에는 파이프의 수 r을 출력한다. 이어서 r줄에 공백으로 구분된 정수 x_j와 y_j를 출력한다. 여기서 , 이다. 이 줄은 입구 게이트 x_j에 들어간 Flubbyplaxmol이 출구 게이트 y_j까지 흐른다는 뜻이다. r줄은 모두 서로 달라야 하며, 입구 게이트를 기준으로, 같으면 출구 게이트를 기준으로 사전순 정렬해야 한다. 빈 줄은 출력하지 않는다.