연산 횟수 세기

시간 제한2초메모리 제한2048 MB

요약

0부터 n-1까지 도는 반복문에서 i가 x일 때 i를 y로 바꾸는 규칙이 주어졌을 때, 수행되는 연산 횟수를 세거나 끝나지 않으면 -1을 출력합니다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 그래프, 구현
정답자: 아직 제출이 없습니다

문제

수업 시간에 Ania가 0부터 $n - 1$ 까지의 모든 정수에 대해 작업을 수행하는 프로그램을 작성했다.

for (int i = 0; i < n; i++) {
    work (i);
}

선생님 Petia는 이 프로그램을 보고, $n$ 의 최댓값이 $10^{9}$ 이므로 실행 시간이 너무 길다고 말했다.

이에 Ania는 일부 수에 대해서만 작업을 하기로 했다. 새 프로그램은 다음과 같다.

for (int i = 0; i < n; i++) {
    if (i == x_1) i = y_1;
    if (i == x_2) i = y_2;
    ...
    if (i == x_k) i = y_k;
    work (i);
}

주어진 $n$ 에 대해 이 프로그램이 몇 번의 연산을 수행하는지 구하고, 프로그램이 종료하는지도 판단하라. 세는 연산은 대입(i = 0, i++, i = y\_1, ...), 비교(i < n, i == x\_1, ...), 그리고 work (i) 호출 자체이다.

입력

입력은 Ania가 작성한 프로그램이다. 형식은 예제와 같다. for가 있는 줄에 여는 중괄호가 있고, 여는 소괄호 앞에는 공백이 있으며, 들여쓰기는 공백 네 칸이다. 줄 끝에는 공백이 없다.

조건문 줄의 개수 $k$ 는 $0 \le k \le 10^{5}$ 이다. 값의 제약은 $0 \le x_i, y_i < n \le 10^{9}$ 이다. 그 밖의 값에는 제약이 없다. work가 있는 줄은 모든 if 줄 뒤에 한 번 나온다.

출력

프로그램이 수행하는 연산의 개수를 출력한다. 프로그램이 종료하지 않으면 -1을 출력한다.

예제2

예제 1

입력

for (int i = 0; i < 3; i++) {
    work (i);
}

예상 출력

예제 2

입력

for (int i = 0; i < 5; i++) {
    if (i == 3) i = 1;
    if (i == 1) i = 3;
    if (i == 3) i = 4;
    work (i);
}

예상 출력