시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB107131024.390%

문제

ntopia는 n마리의 개와 m마리의 고양이가 참여하는 유명한 동물 예능 프로그램을 진행하고 있다. 모든 개는 1번부터 n번까지 번호가 붙어있고, 모든 고양이도 1번부터 m번까지 번호가 붙어있다. 어른들의 사정 때문에 ntopia는 높은 시청률을 만들어야만 했고, 때문에 시청률을 올리기 위한 수많은 편법들을 시도하고 있다.

개와 고양이 사이의 호감도에는 관심 없음, 싫음, 좋음의 3가지 종류가 있다. 신기하게도 호감도에는 대칭성이 있어서, 어떤 고양이가 어떤 개에게 느끼는 호감도는 그 개가 그 고양이에게 느끼는 호감도와 항상 같으며 반대의 경우도 마찬가지이다.

시청률을 올리기 위한 편법으로 아래와 같은 두 가지 종류의 작업을 수행할 수 있다.

  1. 1마리의 개, 그리고 번호가 인접한 2마리의 고양이를 고른다. 고른 동물들 사이에서 2개의 개-고양이 관계가 모두 좋음이면 싫음으로, 모두 싫음이면 좋음으로 바꿀 수 있다.
  2. 1마리의 고양이, 그리고 번호가 인접한 2마리의 개를 고른다. 고른 동물들 사이에서 2개의 개-고양이 관계가 모두 좋음이면 싫음으로, 모두 싫음이면 좋음으로 바꿀 수 있다.


동물들의 관심과 흥미를 빅데이터로 분석하여 가장 좋은 상태를 계산하고 있는 ntopia의 모습

ntopia는 모든 동물들을 분석하여 가장 시청률이 많이 나오는 호감도 상태를 계산하였다. 하지만 동물들 사이의 호감도를 바꾸는 것은 매우 어려운 작업이기 때문에, ntopia가 직접 작업하려던 계획은 실패했다. 결국 ntopia는 한국에서 가장 뛰어난 프로그래머인 여러분에게 도움을 요청했다.

초기 호감도 상태와 ntopia가 만들어야 하는 호감도 상태가 주어졌을 때, 만들 수 있는지의 여부와, 만들 수 있다면 작업의 최소 수행 횟수, 그리고 그 방법을 구하자.

입력

첫 번째 줄에 n, m이 주어진다. (1 ≤ n, m ≤ 100)

두 번째 줄에 초기 상태의 좋음 관계 수 u와 싫음 관계 수 v가 주어진다. (1 ≤ u + v ≤ 500)

세 번째 줄부터 u개의 줄에 좋음 관계의 개 번호 di와 고양이 번호 ci가 주어진다. u+3번째 줄부터 v개의 줄에 싫음 관계의 개 번호 dj와 고양이 번호 cj가 주어진다(1 ≤ di, dj ≤ n, 1 ≤ ci, cj ≤ m).

u+v+3번째 줄부터 만들어야 하는 상태의 정보가 초기 상태의 정보와 같은 방식으로 주어지며, 제한 또한 동일하다.

입력으로 주어지지 않은 관계의 호감도는 “관심없음”임이 보장된다. 한 상태에서 같은 (di, ci) 쌍이 2번 이상 주어지는 경우는 없다.

출력

최종 상태를 만들 수 없다면 첫 번째 줄에 -1을 출력한다.

만들 수 있다면 첫 번째 줄에 최소 횟수 k를 출력한 뒤, 그 이후로 k개의 줄에 호감도를 바꾸는 방법을 출력한다. d번 개와 c, c+1번 고양이를 선택했다면 ”0 d c”를, c번 고양이와 d, d+1번 개를 선택했다면 ”1 c d”를 출력한다(쌍따옴표는 생략).

최소 수행 횟수를 달성하는 방법이 여러가지라면 그 중 아무거나 출력해도 된다.

예제 입력 1

3 4
3 4
1 2
1 3
1 4
2 3
2 4
3 3
3 4
1 6
2 3
1 4
1 3
1 2
2 4
3 3
3 4

예제 출력 1

3
0 1 2
1 3 1
0 1 3