[2021 SCPC 1차 예선]

차이

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



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



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

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

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



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



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



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

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”는 첫번째 종류의 명령이며 라는 정보를 준다. 그 다음 줄은 라는 정보를 준다. 두 정보는 동일한 것임을 알 수 있다. 다음 줄의 “2 2 3”은 에 대한 명령이다. 에서 로의 연결의 예는 등이 있다. 모든 연결에서 계산한 값이 2로 동일함을 알 수 있다. 따라서 이 명령에 대한 답은 2이다. 다음 줄은 이라는 정보를 준다. 다음 명령은 “2 2 3”이다. 에서 로의 가능한 연결인 에 대해 라는 정보를 사용한 계산과 (동등하게 이라는 정보를 사용한 계산의 결과가 서로 다르므로 이 명령에 대한 답은 CF이다. 다음 명령인 “2 5 2”의 경우 에서 로의 가능한 연결이 없으므로 답은 NC이다. 마지막 명령의 답은 -15이다.



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


입력

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

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

이후 차례로   개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 변수의 개수 과 명령의 개수 가 주어진다.

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


출력

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

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

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

입출력예

입력
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

돌아가기