[2021 SCPC 1차 예선]

차이

N개의 변수 X1.,X2,,XN이 있다. 처음에는 Xi들의 값에 대한 어떤 정보도 가지고 있지 않다. K개의 명령이 주어지는데, 명령은 두가지 종류이다. 첫번째 종류는 두 변수의 차이를 알려주는 것이다. 즉, XiXj=d라는 정보를 준다. XjXi=d라는 정보도 주어진 것으로 간주한다. 두번째 종류는 두 변수의 차이를 묻는 것이다. 명령들은 하나하나 순서대로 주어지는 것으로 생각한다.



두번째 종류의 명령에 대한 대답은 다음의 3가지가 있다.



    - 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이가 유일하게 정해지면 그 값을 출력해야 한다.

    - 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 방법이 전혀 없다면 NC를 출력한다. NC의 의미는 Not Connected이다.

    - 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 수 있지만 하나로 정하는 것이 불가능하다면 CF를 출력한다. CF의 의미는 Conflict이다.



위의 조건을 자세히 설명하면 다음과 같다: 두번째 종류의 명령에서 주어진 두 변수를 XiXj라고 하자. Xi에서 Xj로의 연결은 변수의 열인데, 처음이 Xi이고 마지막이 Xj이며 열에서 인접한 모든 쌍이 그 시점까지 첫번째 종류의 명령으로 주어진 것이라야 한다. 인접한 쌍이 첫번째 종류의 명령에서 등장한 순서대로일 필요는 없다. Xi에서 Xj로의 연결은 여러 개가 존재할 수 있음에 주의하라. Xi에서 Xj로의 연결을 따라 계산한다는 것은 다음과 같이 정의된다. [Xi,Xk,,Xj]가 연결이라고 하자. XiXk의 값에 대한 정보가 여러 번 주어진 경우 어떤 것이든 사용할 수 있다. 동일한 연결에 대해서도 계산의 결과는 여러가지일 수가 있다. 선택한 정보가 XiXk=d라면 d의 차이가 최초로 누적된다. Xk이후 Xj에 도달할 때까지 동일한 방식으로 차이를 누적한다. 동일한 연결에 대해서도 계산의 결과는 여러가지일 수가 있음에 주의하라.



Xi에서 Xj로의 가능한 모든 연결에 따라 XiXj의 차이의 모든 가능한 경우를 계산했을 때 전부 동일한 값이 나온다면 위의 첫번째 경우에 해당한다. XiXj의 가능한 연결이 존재하지 않는 경우 위의 두번째 경우에 해당한다. XiXj의 가능한 연결들을 이용해 XiXj의 차이를 계산했을 때 그 결과가 여러가지라면 위의 세번째 경우에 해당한다.



아래 입출력 예의 경우를 보자 입력은 아래와 같다. 

1

5 9

1 2 3 2

1 3 2 -2

2 2 3

1 3 2 -3

2 2 3

1 1 4 7

1 4 5 8

2 5 2

2 5 1



첫 줄의 “1”은 테스트 케이스의 개수이다. 테스트케이스의 첫번째 줄의 “5 9”는 변수가 5개 있으며 명령이 9개 있다는 뜻이다. 다음 줄의 “1 2 3 2”는 첫번째 종류의 명령이며 X2X3=2라는 정보를 준다. 그 다음 줄은 X3X2=2라는 정보를 준다. 두 정보는 동일한 것임을 알 수 있다. 다음 줄의 “2 2 3”은 X2X3에 대한 명령이다. X2에서 X3로의 연결의 예는 [X2,X3],[X2,X3,X2,X3] 등이 있다. 모든 연결에서 계산한 값이 2로 동일함을 알 수 있다. 따라서 이 명령에 대한 답은 2이다. 다음 줄은 X3X2=3이라는 정보를 준다. 다음 명령은 “2 2 3”이다. X2에서 X3로의 가능한 연결인 [X2,X3]에 대해 X2X3=2라는 정보를 사용한 계산과 X3X2=3(동등하게 X2X3=3)이라는 정보를 사용한 계산의 결과가 서로 다르므로 이 명령에 대한 답은 CF이다. 다음 명령인 “2 5 2”의 경우 X5에서 X2로의 가능한 연결이 없으므로 답은 NC이다. 마지막 명령의 답은 -15이다.



위와 같이 정해진 명령들을 처리하는 프로그램을 작성하시오. 


입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,

이후 차례로  T 개의 테스트 케이스가 주어진다. (1T35)

각 테스트 케이스의 첫 줄에는 변수의 개수 N과 명령의 개수 K가 주어진다. (1N100,000,1K200,000)

둘째 줄부터 K개의 각 줄에는 명령이 하나씩 주어진다. 명령의 첫 수가 1인 경우 차이를 알려주는 것이다. “1 i j d”와 같이 주어진 경우 XiXj=d라는 의미이다. 동일한 쌍의 변수에 대해 여러 개의 1번 종류 명령이 주어질 수 있다. 명령의 첫 수가 2인 경우 차이를 묻는 것이다. 즉, “2 i j”와 같이 주어진 경우 XiXj를 묻는 것이다. 두 종류 모두 i와 j가 같을 수도 있다. d의 절대값은 10,000 이하이다.


출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

그 다음 줄부터 각 쿼리에 대한 답을 한 줄에 출력한다.

입출력예

입력
1
5 9
1 2 3 2
1 3 2 -2
2 2 3
1 3 2 -3
2 2 3
1 1 4 7
1 4 5 8
2 5 2
2 5 1
출력
Case #1
2
CF
NC
-15

돌아가기


댓글