자바의 형변환

자바의 클래스끼리는 상속을 통해 자신의 기능 일부를 다른 클래스에 넘겨줄 수 있다. 이때 상속을 받은 클래스는 자식 클래스, 상속을 해 준 클래스는 부모 클래스가 된다. 클래스로 만든 객체는 다른 클래스의 형태로 변환할 수 있으며, 이를 형변환(Casting)이라고 한다. 자식 클래스에서 부모 클래스로 변환하면 업캐스팅(Upcasting), 부모 클래스에서 자식 클래스로 변환하면 다운캐스팅(Downcasting)이라고 부른다. 즉, 자식 클래스와 부모 클래스의 관계에 있으면 형변환이 가능하다. 다운캐스팅은 런타임에 문제를 일으킬 수 있지만 이 문제에서는 고려하지 않는다. 또한 자바는 클래스의 다중 상속을 지원하지 않는다.

예를 들어 number 클래스는 object 클래스를 상속받는다. 따라서 number 클래스는 object 클래스의 자식 클래스이고, object 클래스는 number 클래스의 부모 클래스이다.

자식 클래스가 여러 단계를 거쳐 상속을 받은 경우, 그 자식 클래스에 상속을 해 준 클래스들이 모두 부모 클래스가 된다. 예를 들어 integer 클래스는 number 클래스를 상속받고, number 클래스는 object 클래스를 상속받았으므로, integer 클래스는 number 클래스와 object 클래스를 모두 상속받은 것과 같다. 따라서 integer 클래스와 object 클래스는 부모-자식 관계이며, 두 클래스 사이에 형변환이 가능하다.

입력으로 $N$개의 임의의 클래스 사이의 관계가 주어지고, 검사할 두 클래스의 정보가 주어진다. 두 클래스가 서로 형변환이 가능하면 1을, 그렇지 않으면 0을 출력한다.

첫 줄에 클래스의 수 $N$이 주어진다. ($2 \le N \le 100\ 000$)

다음 $N - 1$개의 줄에 클래스 사이의 관계가 주어진다. $A$, $B$가 순서대로 주어지며, 이는 $A$가 $B$의 자식 클래스라는 뜻이다. $A$와 $B$는 알파벳 소문자로만 이루어진 길이 2 이상 50 이하의 문자열이다.

마지막 줄에는 형변환이 가능한지 확인할 두 클래스가 주어진다. 이 두 클래스는 항상 $N - 1$개 줄의 입력에 나온 클래스이며, 이름은 서로 다르다.

입력으로 주어지는 트리는 루트가 하나인 트리이다.

두 클래스가 형변환이 가능하면 1을, 그렇지 않으면 0을 출력한다.

첫 번째와 두 번째 예시의 클래스 구성도는 아래와 같다.

number와 string의 부모 클래스는 object뿐이므로 number와 string은 서로 형변환할 수 없다. 따라서 첫 번째 예시의 답은 0이다.

반면 integer의 부모 클래스는 number이므로 두 클래스는 서로 형변환이 가능하다. 따라서 두 번째 예시의 답은 1이다.