시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB397967226.966%

문제

현대 모비스는 직원들이 소프트웨어 직무 교육을 이수할 수 있는 소프트웨어 아카데미를 2018년부터 운영하고 있다.

이 소프트웨어 아카데미에서는 총 세 번의 수업이 진행된다. 더 효과적인 학습을 위해 아카데미를 다니고 있는 $N$명의 직원들은 매 수업이 끝난 후 스터디를 진행하고자 한다.

스터디를 같이하는 구성원은 매 수업이 끝난 후 두 직원 간의 합의로 이루어진다. 만약 $a$번 직원과 $b$번 직원이 합의하였다면, 두 직원은 같이 스터디를 하게 된다. 이때 스터디를 같이 하는 직원들의 2명 이상의 모임을 모비스터디라고 한다. $a$번 직원과 $b$번 직원이 합의했고 $b$번 직원과 $c$번 직원 또한 합의했다면, $a$, $b$, $c$번 직원은 모두 같은 모비스터디이다.

굉장한 모비스터디를 다음과 같이 정의하자.

  • 어떤 직원들이 세 번의 스터디에서 모두 같은 모비스터디에 속하고,
  • 그 외의 직원들 중 어떤 직원도 이 모비스터디에 속한 직원들과 세 번의 스터디 모두를 같이 하지 않았다면

이 모비스터디는 굉장한 모비스터디다.

굉장한 모비스터디를 찾자.

입력

첫째 줄에는 아카데미를 다니고 있는 직원의 수 $N\left(1\leq N \leq 100\, 000\right)$이 주어진다.

둘째 줄에는 세 번의 스터디에서 이루어진 합의의 수 $M_{1},M_{2},M_{3}$가 공백으로 구분되어 주어진다. $\left(1\leq M_{1},M_{2},M_{3}\leq 100\,000\right)$

이후 $M_{1}$개의 줄에는 첫 번째 스터디에서 합의한 서로 다른 두 직원의 번호 $a$와 $b$가 공백을 두고 주어진다.

이후 $M_{2}$개의 줄에는 두 번째 스터디에서 합의한 서로 다른 두 직원의 번호 $a$와 $b$가 공백을 두고 주어진다.

이후 $M_{3}$개의 줄에는 세 번째 스터디에서 합의한 서로 다른 두 직원의 번호 $a$와 $b$가 공백을 두고 주어진다.

$\left(a \neq b, 1\leq a,b \leq N \right)$

입력으로 주어지는 모든 값은 정수다.

출력

첫 번째 줄에는 굉장한 모비스터디의 수 $K$를 출력한다.

이후 $K$개의 줄에 걸쳐 굉장한 모비스터디에 포함된 직원들의 번호를 출력한다.

출력 형식은 다음과 같다.

  • 서로 다른 굉장한 모비스터디의 경우 포함된 직원의 최소 번호가 더 작은 굉장한 모비스터디가 먼저 출력되어야한다.
    • 예를 들어 두 굉장한 모비스터디가 각각 $\left\{3,4 \right\}$와 $\left\{1,2,5\right\}$라면 $\left\{1,2,5\right\}$가 먼저 출력되어야 한다.
  • 같은 굉장한 모비스터디에 속한 직원들의 번호가 오름차순으로 정렬되어있어야 한다.
    • 예를 들어 어떤 굉장한 모비스터디가 $\left\{3,2,6\right\}$이라면 $\left\{ 2,3,6 \right\}$과 같이 출력되어야 한다.

예제 입력 1

5
3 4 3
1 2
2 3
4 5
1 2
2 3
3 4
4 5
2 3
1 4
4 5

예제 출력 1

2
2 3
4 5

출처

University > 경인지역 6개대학 연합 > shake! 2022 C번