## Exam Prep

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Java 1.0s
Python 1.0s
Memory limit: 64M
Python 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Despite Bob's best efforts to avoid procrastinating, he still has yet to study for tomorrow's exam! Fortunately, his classmates are very resourceful and have taken notes during class.

In order to get his classmates to share them, he has decided to befriend some of the classmates. Some classmates are more attentive in class and can therefore provide more notes. His class contains people, excluding him, conveniently numbered to , and each classmate has pages of notes. For any integer , every classmate is in 's friend list if there exists a path of direct friendships from to . The resourcefulness of any classmate's friend list is the sum of the values of their friend list.

Initially, the only friend each classmate has is themselves. Bob will then provide you with queries, where each query will be one of the following:

1 a b which means to make classmates a and b friends with each other. Note that friendship is bidirectional.

2 a which means to print the size of a's friend list.

3 a which means to print the resourcefulness of classmate a's friend list.

#### Input Specification

The first line will consist of the two integers and .

The next line will have integers, where the th integer denotes .

The next lines will consist of one query per line in the format described above.

#### Output Specification

For each query of type 2 or 3, print out the answer in a new line.

#### Sample Input

4 5
1 2 1 0
1 1 2
1 1 3
2 1
2 3
3 3

#### Sample Output

3
3
4

#### Explanation

1 is friends with 2 and 3, so both 1 and 3 have three friends. Therefore, the resourcefulness of 3 is .