Informatica Online Judge

  NYPC 자리 배정 [1695 / 069F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 4   Total Tried : 60


The Champion of this Problem (C++) : kdh9949 - ms / 2426byte
My Best Submission (C++) : N/A

[koistudy.net (33rd 김동현)]

Background

2020년, 어느덧 대학생이 된 현수는 어린 나이에도 불구하고 그 뛰어난 정보적 재능을 인정받아 제 5회 NYPC의 진행을 담당하게 되었다.

지난 대회 참가자들이 건의했던 사항을 읽어보던 현수는 자리 배정이 마음에 안 든다는 의견을 다수 보게 되었다.

마음씨가 고운 현수는 참가자의 의견을 최대한 반영하기 위해 본선 참가자 $N$명에게 원하는 자리를 최대 두 개까지 말하라고 공지하였다.

그러면 현수는 모든 참가자가 자신이 원한다고 써 낸 자리 중 하나에 앉도록 각 참가자를 서로 다른 자리에 배정해 줄 예정이었다.

참가자 N명이 응답한 자리 목록을 보던 현수는 하라는 자리 배치는 안 하고 대신 재미있는 문제를 생각해 냈다.

곧 그는 NYPC 관계자들에게 “가능한 모든 자리 배치의 가짓수는 얼마나 될까?”라는 질문을 던졌다.

하지만, 현수 말고 이 문제를 풀어낸 사람은 없었다. 이제, 여러분이 이 문제를 풀어 NYPC를 정복하자!

Input

첫 번째 줄에는 NYPC 참가자 수 $N$이 주어진다.
두 번째 줄부터 $N$줄에 걸쳐 각 줄에는 각 참가자가 선택한 좌석 번호 두 개가 공백으로 구분되어 주어진다.

좌석 번호 두 개가 같을 수도 있다.

[입력값의 정의역]
$1 ≤ N ≤ 300,000$
$1 ≤ 좌석번호 ≤ 300,000$

Output

첫 번째 줄에 조건에 맞는 자리 배정의 가짓수를 $1,000,000,007$ (10억 7)로 나눈 나머지를 출력한다.

IO Example

입력예제
5
1 2
1 4
2 3
2 4
4 5

출력예제
2

설명
2 1
1 4
3 3
4 2
5 5
의 2가지 경우가 가능하다. 다른 경우는 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]