You are given an undirected graph with N vertices and 0 edges. Process Q queries of the following types.

* `0 u v`: Add an edge (u, v).
* `1 u v`: Print 1 if u and v are in the same connected component, 0 otherwise.

Constraints

* 1 \leq N \leq 200,000
* 1 \leq Q \leq 200,000
* 0 \leq u_i, v_i \lt N

Input

Input is given from Standard Input in the following format:


N Q
t_1 u_1 v_1
t_2 u_2 v_2
:
t_Q u_Q v_Q


出力

For each query of the latter type, print the answer.

Example

Input

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3


Output

0
1
0
1
public class Main implements Runnable {

	/** 確保するメモリの大きさ(単位: MB) */
	private static final long MEMORY = 56;

	public void solve(AtCoder.Input in, AtCoder.Output out, String[] args) {
		// write code
		int N = in.nextInt(), Q = in.nextInt();
		AtCoder.DisjointSetUnion dsu = new AtCoder.DisjointSetUnion(N);
		while(Q --> 0) {
			int t = in.nextInt(), u = in.nextInt(), v = in.nextInt();
			if (t == 0) {
				dsu.merge(u, v);
			} else {
				out.println(dsu.isSame(u, v) ? 1 : 0);
			}
		}
	}

	private final String[] args;

	public static void main(String[] args) {
		Thread.setDefaultUncaughtExceptionHandler((t, e) -> {
			e.printStackTrace();
			System.exit(1);
		});
		new Thread(null, new Main(args), "", MEMORY * 1048576L).start();
	}

	public Main(String[] args) {
		this.args = args;
	}

	@Override
	public void run() {
		try (AtCoder.Input in = new AtCoder.Input(System.in); AtCoder.Output out = new AtCoder.Output(System.out)) {
			solve(in, out, args);
			out.flush();
		} ;
	}

	public static class AtCoder {

		public static final class Input extends java.io.InputStream {

			private final java.io.InputStream in;
			private final byte[] buffer = new byte[1024];
			private int read = 0;
			private int length = 0;

			public Input(java.io.InputStream in) {
				this.in = in;
			}

			@Override
			public int available() {
				try {
					return in.available();
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
				return 0;
			}

			@Override
			public void close() {
				try {
					in.close();
					read = length = 0;
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
			}

			@Override
			public int read() {
				if (hasNextByte()) return nextByte();
				return 0;
			}

			private boolean hasNextByte() {
				if (read < length) return true;
				read = 0;
				try {
					length = in.read(buffer);
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
				return length > 0;
			}

			private static boolean isPrintableChar(byte c) {
				return 32 < c || c < 0;
			}

			private static boolean isNumber(int c) {
				return '0' <= c && c <= '9';
			}

			private boolean readNewLine() {
				if (hasNextByte()) {
					if (buffer[read] == '\r') {
						++read;
						if (hasNextByte() && buffer[read] == '\n') ++read;
						return true;
					}
					if (buffer[read] == '\n') {
						++read;
						return true;
					}
				}
				return false;
			}

			public boolean hasNext() {
				while (hasNextByte() && !isPrintableChar(buffer[read]))
					read++ ;
				return hasNextByte();
			}

			public boolean nextBoolean() {
				return Boolean.valueOf(next());
			}

			public byte nextByte() {
				if (hasNextByte()) return buffer[read++ ];
				throw new java.util.NoSuchElementException();
			}

			public short nextShort() {
				if (!hasNext()) throw new java.util.NoSuchElementException();
				short n = 0;
				try {
					byte b = nextByte();
					if (b == '-') {
						while (isNumber(b = nextByte()))
							n = (short)(n * 10 + '0' - b);
						return n;
					} else if (!isNumber(b)) throw new NumberFormatException();
					do
						n = (short)(n * 10 + b - '0');
					while (isNumber(b = nextByte()));
					return n;
				} catch (java.util.NoSuchElementException e) {
					return n;
				}
			}

			public int nextInt() {
				if (!hasNext()) throw new java.util.NoSuchElementException();
				int n = 0;
				try {
					byte b = nextByte();
					if (b == '-') {
						while (isNumber(b = nextByte()))
							n = n * 10 + '0' - b;
						return n;
					} else if (!isNumber(b)) throw new NumberFormatException();
					do
						n = n * 10 + b - '0';
					while (isNumber(b = nextByte()));
					return n;
				} catch (java.util.NoSuchElementException e) {
					return n;
				}
			}

			public long nextLong() {
				if (!hasNext()) throw new java.util.NoSuchElementException();
				long n = 0;
				try {
					byte b = nextByte();
					if (b == '-') {
						while (isNumber(b = nextByte()))
							n = n * 10 + '0' - b;
						return n;
					} else if (!isNumber(b)) throw new NumberFormatException();
					do
						n = n * 10 + b - '0';
					while (isNumber(b = nextByte()));
					return n;
				} catch (java.util.NoSuchElementException e) {
					return n;
				}
			}

			public float nextFloat() {
				return Float.parseFloat(next());
			}

			public double nextDouble() {
				return Double.parseDouble(next());
			}

			public char nextChar() {
				byte b = nextByte();
				if ((b & 0x80) == 0) return (char)b;
				if ((b & 0x20) == 0) return (char)((b & 0x1F) << 6 | (nextByte() & 0x3F));
				return (char)((b & 0xF) << 12 | (nextByte() & 0x3F) << 6 | (nextByte() & 0x3F));
			}

			public String next() {
				if (!hasNext()) throw new java.util.NoSuchElementException();
				StringBuilder sb = new StringBuilder();
				do
					sb.append(nextChar());
				while (hasNextByte() && isPrintableChar(buffer[read]));
				return sb.toString();
			}

			public String nextLine() {
				StringBuilder sb = new StringBuilder();
				while (!readNewLine())
					sb.append(nextChar());
				return sb.toString();
			}

		}

		public static final class Output extends java.io.OutputStream {

			private final java.io.OutputStream out;
			private final byte[] buffer = new byte[1 << 16];
			private int read = 0;
			private boolean autoFlush = true;
			private static final int READ_STRING_TO_BYTE_ARRAY;

			public Output(java.io.OutputStream out) {
				this.out = out;
			}

			public void setAutoFlush(boolean autoFlush) {
				this.autoFlush = autoFlush;
			}

			static {
				int flag = -1;
				try {
					String test = "test";
					java.lang.reflect.Field strValueField = test.getClass().getDeclaredField("value");
					strValueField.setAccessible(true);
					Object value = strValueField.get(test);
					strValueField.setAccessible(false);
					if (value instanceof byte[]) flag = 0;
					else flag = 1;
				} catch (Exception e) {
				}
				READ_STRING_TO_BYTE_ARRAY = flag;
			}

			@Override
			public void close() {
				try {
					flush();
					out.close();
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
			}

			@Override
			public void flush(){
				try {
					write();
					out.flush();
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
			}

			@Override
			public void write(byte[] b) {
				try {
					out.write(b);
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
			}

			@Override
			public void write(byte[] b, int off, int len) {
				try {
					out.write(b, off, len);
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
			}

			@Override
			public void write(int b) {
				try {
					out.write(b);
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
			}

			private void write() {
				write(buffer, 0, read);
				read = 0;
			}

			public void print(boolean b) {
				if (b) {
					print((byte)'t');
					print((byte)'r');
					print((byte)'u');
					print((byte)'e');
				} else {
					print((byte)'f');
					print((byte)'a');
					print((byte)'l');
					print((byte)'s');
					print((byte)'e');
				}
			}

			public void print(byte b) {
				if (read == buffer.length) write();
				buffer[read ++] = b;
			}

			public void print(short s) {
				if (s < 0) {
					print((byte)'-');
					if (s == -32768) {
						print((byte)'3');
						print((byte)'2');
						print((byte)'7');
						print((byte)'6');
						print((byte)'8');
						return;
					}
					s = (short)-s;
				}
				if (s >= 100) {
					if (s >= 1000) {
						if (s >= 10000) {
							print((byte)(s / 10000 % 10 + '0'));
						}
						print((byte)(s / 1000 % 10 + '0'));
					}
					print((byte)(s / 100 % 10 + '0'));
					print((byte)(s / 10 % 10 + '0'));
				} else {
					if (s >= 10) print((byte)(s / 10 % 10 + '0'));
				}
				print((byte)(s % 10 + '0'));
			}

			public void print(int i) {
				if (i < 0) {
					print((byte)'-');
					if (i == -2147483648) {
						print((byte)'2');
						print((byte)'1');
						print((byte)'4');
						print((byte)'7');
						print((byte)'4');
						print((byte)'8');
						print((byte)'3');
						print((byte)'6');
						print((byte)'4');
						print((byte)'8');
						return;
					}
					i = -i;
				}
				if (i >= 1000000000) print((byte)(i / 1000000000 % 10 + '0'));
				if (i >= 100000000) print((byte)(i / 100000000 % 10 + '0'));
				if (i >= 10000000) print((byte)(i / 10000000 % 10 + '0'));
				if (i >= 1000000) print((byte)(i / 1000000 % 10 + '0'));
				if (i >= 100000) print((byte)(i / 100000 % 10 + '0'));
				if (i >= 10000) print((byte)(i / 10000 % 10 + '0'));
				if (i >= 1000) print((byte)(i / 1000 % 10 + '0'));
				if (i >= 100) print((byte)(i / 100 % 10 + '0'));
				if (i >= 10) print((byte)(i / 10 % 10 + '0'));
				print((byte)(i % 10 + '0'));
			}

			public void print(long l) {
				if (l < 0) {
					print((byte)'-');
					if (l == -9223372036854775808L) {
						print((byte)'9');
						print((byte)'2');
						print((byte)'2');
						print((byte)'3');
						print((byte)'3');
						print((byte)'7');
						print((byte)'2');
						print((byte)'0');
						print((byte)'3');
						print((byte)'6');
						print((byte)'8');
						print((byte)'5');
						print((byte)'4');
						print((byte)'7');
						print((byte)'7');
						print((byte)'5');
						print((byte)'8');
						print((byte)'0');
						print((byte)'8');
						return;
					}
					l = -l;
				}
				if (l >= 1000000000000000000L) print((byte)(l / 1000000000000000000L % 10 + '0'));
				if (l >= 100000000000000000L) print((byte)(l / 100000000000000000L % 10 + '0'));
				if (l >= 10000000000000000L) print((byte)(l / 10000000000000000L % 10 + '0'));
				if (l >= 1000000000000000L) print((byte)(l / 1000000000000000L % 10 + '0'));
				if (l >= 100000000000000L) print((byte)(l / 100000000000000L % 10 + '0'));
				if (l >= 10000000000000L) print((byte)(l / 10000000000000L % 10 + '0'));
				if (l >= 1000000000000L) print((byte)(l / 1000000000000L % 10 + '0'));
				if (l >= 100000000000L) print((byte)(l / 100000000000L % 10 + '0'));
				if (l >= 10000000000L) print((byte)(l / 10000000000L % 10 + '0'));
				if (l >= 1000000000L) print((byte)(l / 1000000000L % 10 + '0'));
				if (l >= 100000000L) print((byte)(l / 100000000L % 10 + '0'));
				if (l >= 10000000L) print((byte)(l / 10000000L % 10 + '0'));
				if (l >= 1000000L) print((byte)(l / 1000000L % 10 + '0'));
				if (l >= 100000L) print((byte)(l / 100000L % 10 + '0'));
				if (l >= 10000L) print((byte)(l / 10000L % 10 + '0'));
				if (l >= 1000L) print((byte)(l / 1000L % 10 + '0'));
				if (l >= 100L) print((byte)(l / 100L % 10 + '0'));
				if (l >= 10L) print((byte)(l / 10L % 10 + '0'));
				print((byte)(l % 10 + '0'));
			}

			public void print(float f) {
				print(Float.toString(f));
			}

			public void print(double d) {
				print(Double.toString(d));
			}

			public void print(double d, int n) {
				if (d < 0) {
					print((byte)'-');
					d = -d;
				}
				d += Math.pow(10, -n) / 2;
				long l = (long)d;
				print(l);
				print((byte)'.');
			        d -= l;
			        for(int i = 0;i < n;i++){
			            d *= 10;
			            int in = (int)d;
			            print((byte)(in + '0'));
			            d -= in;
			        }
			}

			public void print(char c) {
				if (c < 0x80) {
					print((byte)c);
				} else if (c < 0x07FF) {
					print((byte)(c >> 6 & 0x3F | 0x80));
					print((byte)(c & 0x3F | 0x80));
				} else {
					print((byte)(c >> 12 & 0xF | 0xE0));
					print((byte)(c >> 6 & 0x3F | 0x80));
					print((byte)(c & 0x3F | 0x80));
				}
			}

			public void print(char[] s) {
				for (char i : s) print(i);
			}

			public void print(String s) {
				try {
					if (READ_STRING_TO_BYTE_ARRAY == 0) {
							java.lang.reflect.Field strValueField = s.getClass().getDeclaredField("value");
							strValueField.setAccessible(true);
							byte[] c = (byte[])strValueField.get(s);
							strValueField.setAccessible(false);
							strValueField = s.getClass().getDeclaredField("coder");
							strValueField.setAccessible(true);
							byte coder = (byte)strValueField.get(s);
							strValueField.setAccessible(false);
							if (coder == 0) {
								for (byte b : c) print(b);
							} else if (coder == 1) {
								for (int i = 0;i < c.length;i += 2) print((char)(c[i] | c[i + 1] << 8));
							} else {
								print(s.toCharArray());
							}
					} else if (READ_STRING_TO_BYTE_ARRAY == 1) {
						java.lang.reflect.Field strValueField = s.getClass().getDeclaredField("value");
						strValueField.setAccessible(true);
						print((char[])strValueField.get(s));
						strValueField.setAccessible(false);
					} else {
						print(s.toCharArray());
					}
				} catch (Exception e) {
					print(s.toCharArray());
				}
			}

			public void print(Object o) {
				print(o.toString());
			}

			public void printf(java.util.Locale l, String format, Object... args) {
				print(String.format(l, format, args));
			}

			public void printf(String format, Object... args) {
				print(String.format(format, args));
			}

			public void println() {
				print((byte)'\n');
				if (autoFlush) flush();
			}

			public void println(boolean b) {
				print(b);
				println();
			}

			public void println(byte b) {
				print(b);
				println();
			}

			public void println(short s) {
				print(s);
				println();
			}

			public void println(int i) {
				print(i);
				println();
			}

			public void println(long l) {
				print(l);
				println();
			}

			public void println(float f) {
				print(f);
				println();
			}

			public void println(double d) {
				print(d);
				println();
			}

			public void println(double d, int n) {
				print(d, n);
				println();
			}

			public void println(char c) {
				print(c);
				println();
			}

			public void println(char[] s) {
				print(s);
				println();
			}

			public void println(String s) {
				print(s);
				println();
			}

			public void println(Object o) {
				print(o);
				println();
			}

			public Output append(char c) {
				print(c);
				return this;
			}

			public Output append(CharSequence csq) {
				if (csq == null) csq = "null";
				print(csq.toString());
				return this;
			}

			public Output append(CharSequence csq, int start, int end) {
				if (csq == null) csq = "null";
				print(csq.subSequence(start, end).toString());
				return this;
			}
		}

		public static final class DisjointSetUnion {
			private final int[] parent;
			DisjointSetUnion(int n) {
				parent = new int[n];
				java.util.Arrays.fill(parent, -1);
			}

			public int getLeader(int a) {
				int p1, p2;
				while((p1 = parent[a]) >= 0) {
					if ((p2 = parent[p1]) >= 0) a = parent[a] = p2;
					else return p1;
				}
				return a;
			}

			public int merge(int a, int b) {
				a = getLeader(a);
				b = getLeader(b);
				if (a == b) return a;
				if (parent[a] < parent[b]) {
					parent[b] += parent[a];
					parent[a] = b;
					return b;
				}
				parent[a] += parent[b];
				parent[b] = a;
				return a;
			}

			public boolean isSame(int a, int b) {
				return getLeader(a) == getLeader(b);
			}

			public int getSize(int a) {
				return -parent[getLeader(a)];
			}

			public java.util.ArrayList<java.util.ArrayList<Integer>> getGroups() {
				Object[] group = new Object[parent.length];
				java.util.ArrayList<java.util.ArrayList<Integer>> ret = new java.util.ArrayList<>();
				for (int i = 0;i < parent.length;++ i) {
					int leader = getLeader(i);
					Object put = group[leader];
					if (put == null) {
						java.util.ArrayList<Integer> list = new java.util.ArrayList<>();
						list.add(i);
						ret.add(list);
						group[leader] = list;
					} else {
						@SuppressWarnings("unchecked")
						java.util.ArrayList<Integer> list = (java.util.ArrayList<Integer>) put;
						list.add(i);
					}
				}
				return ret;
			}
		}
	}
}
