문제

마법세계인 "한국정보기술진흥원"에는 번부터 번까지 개의 마법 원소가 있습니다. 몇 가지 원소들은 서로 만났을 때 상호작용이 일어납니다. 상호작용은 총 가지가 있고, 번째 방식의 상호작용은 번 원소와 번 원소가 만날 때 일어납니다.

한국정보기술진흥원의 학자들은 마법세계에 대한 깊은 고찰 끝에, 매우 조화롭고 아름다운 상수 를 발견하였습니다. 이들은 의 위대함을 기리기 위해서, 다음 두 조건 중 하나 이상을 만족하도록 각 원소들에 색상을 부여하고자 합니다.

1. 음의 조건: 각 원소에 번 색상 중 하나를 부여해야 하며, 상호작용이 일어나는 두 원소는 다른 색상이어야 합니다.
2. 양의 조건: 각 원소에 번 색상 중 하나를 부여해야 하며, 부터 번까지 서로 다른 두 색상을 고르면, 두 색상이 각각 부여되어 있으면서 상호작용이 일어나는 두 원소를 찾을 수 있어야 합니다.

두 가지 조건 중 하나 이상을 만족하도록 색상을 부여할 수 있는지 판단하고, 가능하다면 각 원소에 색상을 부여해 봅시다.

입력

첫 번째 줄에 세 양의 정수 가 공백으로 구분되어 주어집니다.

이후 개의 줄에 걸쳐 번째 줄에는 번째 방식의 상호작용을 의미하는 두 양의 정수 가 공백으로 구분되어 주어집니다.

출력

만약 두 조건 중 하나 이상을 만족하도록 원소들에 색상을 부여할 수 없다면, 첫 번째 줄에 을 출력합니다.

이외의 경우, 첫 번째 줄에 만족하는 조건의 번호를 출력하고, 두 번째 줄에 번, 번, , 번 원소에 부여한 색상의 번호를 공백으로 구분하여 출력합니다. 음의 조건은 번, 양의 조건은 번이며 둘 모두를 만족하는 경우 어느 쪽으로 출력해도 됩니다.

노트

• 에 대해,
• 에 대해,