스마트한 프로도

직장인 프로도는 오늘도 열심히 일한다. 회사에서 인정받는 프로도는 직장 상사에게 문제를 풀어 달라는 요청을 받았다. 문제를 읽은 프로도는 혼자 풀긴 어려운 문제로 보여 여러분에게 도움을 요청하였다. 상사가 전달한 문제는 아래와 같다.
그래프 G에 대해서, 서로 다른 두 정점 사이에 간선이 존재한다면 단지 한 간선만 존재한다. 또한 동일한 정점을 연결하는 간선(셀프 루프)은 존재하지 않는다. G의 두 간선 e_1과 e_2가 인접하다면, e_1이 연결하는 두 정점 중 하나는 e_2가 연결하는 정점과 일치한다. 그래프 G의 매칭 M은 간선들의 집합이고 M에 속하는 임의의 두 간선은 서로 인접하지 않다. 여기서, 공집합은 매칭임에 주목하자.
그래프 G와 정수 k에 대해서, 초기에 |M_0|≥k이고 |M_t|≥k 인 두 매칭 M_0와 M_t가 주어진다. 우리는 매칭 M_0에서 G의 간선을 추가하거나 또는 삭제해서 M_0를 변환한다. 변환의 한 단계에서는 하나의 간선을 추가하거나 삭제할 수 있다. 이렇게 해서 변환된 간선들의 집합 M_1은 다시 매칭이 되어야 한다. 다시 말해서, 각 변환 단계의 결과물은 매칭이어야 한다. 따라서 i번째 단계에서는 매칭 M_i-1를 매칭 M_i로 변환하게 된다.
이런 식으로 M_0에서 시작해서 중간 매칭들로의 변환 단계들을 거쳐서 마지막에 M_t를 만들어야 한다. 다시 말해서, p번의 단계를 거쳐 만들어진 매칭 M_p에 대해서, M_p = M_t를 만족하면 된다. 하지만 중간에 만들어지는 M_i (0 < i < p)는 크기에 제한이 있어서 |M_i| ≥ k-2를 만족해야만 한다.
매칭 M_0에서 M_t로 위의 조건들을 만족하면서 항상 변환할 수 있다는 것이 잘 알려져 있다. 따라서 여러분은 그 변환 과정을 리턴하는 프로그램을 작성하여야 한다.
예를 들어, 아래 그림에서 초기 매칭 M_0 = {e_3, e_6}이고 마지막 매칭 M_t = {e_2, e_4}이고, k = 2 인 경우이다. 그림에서와 같이 간선들을 추가하거나 삭제하면, M_0에서 M_t로 변환할 수 있다.

입력 형식

입력은 총 9가지의 변수로 주어진다. n과 m은 각각 그래프 G의 정점과 간선의 수이다. 그래프 G의 정점들은 1부터 n까지의 정수로, 간선들은 1부터 m까지의 정수로 나타낸다. a와 b는 각각 크기가 m인 1차원 배열로, 간선이 잇는 두 점을 나타낸다. i번째 간선이 잇는 두 정점의 번호가 a와 b의 i번째 원소가 된다. k는 문제에서 설명된 것과 같다. m1과 m2는 각각 초기 매칭 M_0의 크기, 마지막 매칭 M_t의 크기이다. e1과 e2는 각각 M_0와 M_t에 속하는 간선의 정보를 나타내는 1차원 배열이며, 각각의 원소의 개수는 m1과 m2이다. 제한조건은 다음과 같다.

• 1 <= n <= 100,000
• 1 <= m <= 1,000,000
• 1 <= k <= 50,000
• m1 >= k, m2 >= k

출력 형식

리턴 타입은 2차원 정수 배열이다. 매칭 M_0에서 M_t로 변환하는데 p단계가 걸린다고 할 때, 배열의 크기는 p × 2가 되어야 한다. 각 행의 첫 번째 원소는 0 또는 1로, 0이면 간선을 삭제했음을 의미하며 1이면 간선을 추가했음을 의미한다. 두 번째 원소는 추가 또는 삭제하는 간선의 번호이다. 답이 될 수 있는 변환이 여러 가지인 경우에는 그중 한 가지를 리턴하면 된다.

알림

이 문제의 경우 같은 입력에 대해 정답이 여러 개 존재할 수 있으나, ‘실행’을 눌러 예제 입출력에 대해 테스트를 진행할 때 등록된 한 가지 답만 정답으로 처리되고 있습니다. ‘코드 채점’을 눌러 제출할 시에는 올바르게 채점되니 참고하여 주시기 바랍니다.