Đồ thị thông tin

Điểm: 7,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một công ty có $n$ nhân viên, được đánh số từ $1$ đến $n$ . Ban đầu không nhân viên nào có sếp. Trong $m$ ngày tiếp theo, mỗi ngày diễn ra đúng một trong ba loại sự kiện sau:

Loại 1 — 1 x y: nhân viên $y$ trở thành sếp trực tiếp của nhân viên $x$ . Ngay trước sự kiện này, $x$ chưa có sếp.
Loại 2 — 2 x: nhân viên $x$ nhận được một bưu kiện tài liệu và ký vào đó, sau đó chuyển bưu kiện lên cho sếp trực tiếp của mình. Sếp ký rồi tiếp tục chuyển lên cấp trên. Quá trình kết thúc khi bưu kiện tới một nhân viên không có sếp (người đó ký xong rồi gửi vào kho lưu trữ). Các bưu kiện được đánh số liên tiếp $1, 2, 3, \dots$ theo thứ tự xuất hiện.
Loại 3 — 3 x i: hỏi xem nhân viên $x$ có ký vào bưu kiện thứ $i$ hay không.

Mỗi sự kiện loại 1 không tạo ra chu trình trong quan hệ "sếp", do đó cấu trúc luôn là một rừng có hướng (mỗi cạnh đi từ nhân viên lên sếp).

Bạn hãy trả lời tất cả các truy vấn loại 3.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng nêu trên.

Đảm bảo có ít nhất một sự kiện loại 3, và với mỗi truy vấn loại 3, chỉ số bưu kiện $i$ không vượt quá số bưu kiện đã được gửi đi tính đến thời điểm truy vấn.

Dữ liệu ra

Với mỗi sự kiện loại 3, in ra YES nếu nhân viên đã ký vào bưu kiện tương ứng, ngược lại in ra NO.

Ràng buộc

$1 \leq n, m \leq 10^{5}$
$1 \leq x, y \leq n$
Tại thời điểm xuất hiện sự kiện loại 1 với $x$ , nhân viên $x$ chưa có sếp.
Hệ thống không bao giờ có chu trình.

Ví dụ

Input	Output	Giải thích
4 9 1 4 3 2 4 3 3 1 1 2 3 2 2 3 1 2 1 3 1 2 2 3 1 3	YES NO YES	Bưu kiện 1: nhân viên 4 ký, chuyển lên 3 (sếp của 4). 3 ký. Vậy 3 có ký bưu kiện 1 → YES. Bưu kiện 2: nhân viên 2 ký, chuyển lên 3 (sếp của 2). 3 ký rồi dừng. 1 không ký → NO. Bưu kiện 3: lúc này 3 đã có sếp là 1, nên dây chuyền là 2 → 3 → 1. 1 có ký → YES.
1 2 2 1 3 1 1	YES	Chỉ có một nhân viên 1, không có sếp. Bưu kiện 1 do 1 ký rồi gửi kho.

Bình luận

Không có bình luận tại thời điểm này.