IOI 2022 - Ngày 2 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	IOI 2022 - Digital Circuit	100 (p)	4.0s	2G
2	IOI 2022 - Rarest Insects	100 (p)	2.0s	2G
3	IOI 2022 - Thousands Islands	100 (p)	1.0s	2G

1. IOI 2022 - Digital Circuit

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 2G Input: bàn phím Output: màn hình

Có một mạch điện, bao gồm $N + M$ cổng được đánh số từ $0$ đến $N + M - 1$. Các cổng từ $0$ đến $N - 1$ là các cổng ngưỡng, trong khi các cổng từ $N$ đến $N + M - 1$ là các cổng nguồn.

Mỗi cổng, ngoại trừ cổng $0$, là một đầu vào cho đúng một cổng ngưỡng. Cụ thể, với mỗi $i$ sao cho $1 \le i \le N + M - 1$, cổng $i$ là một đầu vào cho cổng $P[i]$, với $0 \le P[i] \le N - 1$. Lưu ý là ta còn có $P[i] < i$. Thêm nữa, giả thiết $P[0] = -1$. Mỗi cổng ngưỡng có một hoặc nhiều đầu vào. Các cổng nguồn không có bất kỳ đầu vào nào.

Mỗi cổng có một trạng thái là $0$ hoặc $1$. Trạng thái ban đầu của các cổng nguồn được cho bởi mảng $A$ gồm $M$ số nguyên. Nghĩa là, với mỗi $j$ sao cho $0 \le j \le M - 1$, trạng thái ban đầu của cổng nguồn $N + j$ là $A[j]$.

Trạng thái của mỗi cổng ngưỡng phụ thuộc vào trạng thái các đầu vào của nó và được xác định như sau. Đầu tiên, mỗi cổng ngưỡng được gán một tham số ngưỡng. Tham số được gán cho cổng ngưỡng có $c$ đầu vào phải là một số nguyên trong khoảng từ $1$ đến $c$ (bao gồm cả hai đầu mút). Khi đó, trạng thái của cổng ngưỡng với tham số $p$ là $1$, nếu ít nhất $p$ đầu vào trong các đầu vào của nó có trạng thái $1$ và có trạng thái $0$ nếu ngược lại.

Ví dụ, giả sử có $N = 3$ cổng ngưỡng và $M = 4$ cổng nguồn. Các đầu vào cho cổng $0$ là các cổng $1$ và $6$, các đầu vào cho cổng $1$ là các cổng $2$, $4$ và $5$, và đầu vào duy nhất cho cổng $2$ là cổng $3$.

Ví dụ này được minh họa trong hình sau.

Giả sử các cổng nguồn $3$ và $5$ có trạng thái $1$, trong khi các cổng nguồn $4$ và $6$ có trạng thái $0$. Giả sử ta gán các tham số $1$, $2$ và $2$ tương ứng cho các cổng ngưỡng $2$, $1$ và $0$. Trong trường hợp này, cổng $2$ có trạng thái $1$, cổng $1$ có trạng thái $1$ và cổng $0$ có trạng thái $0$. Việc gán các giá trị tham số và trạng thái này được minh họa trong hình sau. Các cổng có trạng thái là $1$ được đánh dấu bởi màu đen.

Trạng thái của các cổng nguồn sẽ có $Q$ lần cập nhật. Mỗi lần cập nhật được mô tả bởi hai số nguyên $L$ và $R$ ($N \le L \le R \le N + M - 1$) và chuyển đổi trạng thái của tất cả các cổng nguồn được đánh số từ $L$ đến $R$, bao gồm cả hai đầu mút. Nghĩa là, với mỗi $i$ sao cho $L \le i \le R$, cổng nguồn $i$ thay đổi trạng thái của nó thành $1$, nếu trạng thái của nó là $0$ hoặc thành $0$, nếu trạng thái của nó là $1$. Trạng thái mới của mỗi cổng được chuyển đổi không thay đổi cho đến khi nó có thể được chuyển đổi bởi một trong các lần cập nhật sau đó.

Nhiệm vụ của bạn là sau mỗi lần cập nhật, đếm xem có bao nhiêu cách gán tham số khác nhau cho các cổng ngưỡng để cổng $0$ có trạng thái $1$. Hai cách gán được coi là khác nhau nếu tồn tại ít nhất một cổng ngưỡng mà tham số của nó có giá trị khác nhau trong cả hai cách gán. Vì số lượng cách có thể lớn, bạn cần tính phần dư trong phép chia cho $1\;000\;002\;022$.

Lưu ý trong ví dụ trên, có $6$ cách gán tham số khác nhau cho các cổng ngưỡng, vì các cổng $0$, $1$ và $2$ có các đầu vào tương ứng là $2$, $3$ và $1$. Ở $2$ trong số $6$ cách gán này, cổng $0$ có trạng thái $1$.

Chi tiết cài đặt

Nhiệm vụ của bạn là cài đặt hai hàm sau.

C++

void init(int N, int M, std::vector<int> P, std::vector<int> A);

$N$: số lượng các cổng ngưỡng.
$M$: số lượng các cổng nguồn.
$P$: mảng $N+M$ phần tử mô tả các đầu vào cho các cổng ngưỡng.
$A$: mảng $M$ phần tử mô tả các trạng thái ban đầu của các cổng nguồn.
Hàm này được gọi đúng một lần, trước bất kỳ lời gọi hàm count_ways nào.

C++

int count_ways(int L, int R);

$L$, $R$: phạm vi chỉ số các cổng nguồn mà có các trạng thái được chuyển đổi.
Hàm này trước tiên cần thực hiện các lần cập nhật, và tiếp theo trả về phần dư của số cách gán các tham số cho các cổng ngưỡng trong phép chia cho $1\;000\;002\;022$, dẫn đến cổng $0$ có trạng thái $1$.
Hàm này được gọi đúng $Q$ lần.

Ví dụ

Xét chuỗi các lời gọi sau:

C++

init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])

Ví dụ này được minh họa trong phần mô tả bài toán ở trên.

C++

count_ways(3, 4)

Hàm này chuyển đổi trạng thái của cổng $3$ và $4$, tức là trạng thái của cổng $3$ trở thành $0$ và trạng thái của cổng $4$ trở thành $1$. Hai cách gán các tham số dẫn đến cổng $0$ có trạng thái $1$ được minh họa trong các hình sau.

Cách $1$	Cách $2$

Trong tất cả các cách gán tham số khác, cổng $0$ có trạng thái $0$. Vì vậy, hàm cần trả về $2$.

C++

count_ways(4, 5)

Hàm này chuyển đổi trạng thái của các cổng $4$ và $5$. Kết quả là, tất cả các cổng nguồn đều có trạng thái $0$ và đối với bất kỳ cách gán tham số nào, cổng $0$ có trạng thái $0$. Vì vậy, hàm cần trả về $0$.

C++

count_ways(3, 6)

Hàm này thay đổi trạng thái của tất cả các cổng nguồn thành $1$. Kết quả là, đối với bất kỳ cách gán tham số nào, cổng $0$ có trạng thái $1$. Vì vậy, hàm cần trả về $6$.

Ràng buộc

$1 \le N, M \le 100\;000$
$1 \le Q \le 100\;000$
$P[0] = -1$
$0 \le P[i] < i$ và $P[i] \le N - 1$ (với mỗi $i$ sao cho $1 \le i \le N + M - 1$)
Mỗi cổng ngưỡng có ít nhất một đầu vào (với mỗi $i$ sao cho $0 \le i \le N - 1$ tồn tại một chỉ số $x$ sao cho $i < x \le N + M - 1$ và $P[x] = i$).
$0 \le A[j] \le 1$ (với mỗi $j$ sao cho $0 \le j \le M - 1$)
$N \le L \le R \le N + M - 1$

Phân nhóm

(2 điểm) $N = 1$, $M \le 1000$, $Q \le 5$
(7 điểm) $N, M \le 1000$, $Q \le 5$, mỗi cổng ngưỡng có đúng hai đầu vào.
(9 điểm) $N, M \le 1000$, $Q \le 5$
(4 điểm) $M = N + 1$, $M = 2^z$ (với một số nguyên dương $z$ nào đó), $P[i] = \lfloor\frac{i - 1}{2}\rfloor$ (với mỗi $i$ sao cho $1 \le i \le N + M - 1$), $L = R$
(12 điểm) $M = N + 1$, $M = 2^z$ (với một số nguyên dương $z$ nào đó), $P[i] = \lfloor\frac{i - 1}{2}\rfloor$ (với mỗi $i$ sao cho $1 \le i \le N + M - 1$)
(27 điểm) Mỗi cổng ngưỡng có đúng hai đầu vào.
(28 điểm) $N, M \le 5000$
(11 điểm) Không có ràng buộc gì thêm.

Trình chấm mẫu

Trình chấm mẫu đọc đầu vào theo định dạng sau:

dòng $1$: $N \; M \; Q$
dòng $2$: $P[0] \; P[1] \; \ldots \; P[N + M - 1]$
dòng $3$: $A[0] \; A[1] \; \ldots \; A[M - 1]$
dòng $4 + k$ ($0 \le k \le Q - 1$): $L \; R$ cho lần cập nhật thứ $k$

Trình chấm mẫu in kết quả của bạn theo định dạng sau:

dòng $1 + k$ ($0 \le k \le Q - 1$): giá trị trả về của count_ways cho lần cập nhật thứ $k$

Nguồn: Đề thi chính thức IOI 2022, bản tiếng Việt, giấy phép CC-BY.

2. IOI 2022 - Rarest Insects

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 2G Input: bàn phím Output: màn hình

Có $N$ con côn trùng, được đánh số từ $0$ đến $N - 1$, chạy quanh nhà của Pak Blangkon. Mỗi con côn trùng thuộc một loài, là một số nguyên từ $0$ đến $10 ^ 9$ bao gồm cả hai đầu mút. Có thể có nhiều con côn trùng cùng một loài.

Giả thiết các con côn trùng được nhóm theo loài. Ta định nghĩa lực lượng của loài côn trùng thường gặp nhất là số lượng con côn trùng trong nhóm có số lượng con côn trùng nhiều nhất. Tương tự, lực lượng của loài côn trùng hiếm nhất là số lượng con côn trùng trong nhóm có số lượng con côn trùng ít nhất.

Ví dụ, có $11$ con côn trùng, thuộc các loài tương ứng là $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$. Trong trường hợp này, lực lượng của loài côn trùng thường gặp nhất là $3$. Các loài có số lượng con côn trùng nhiều nhất là loài $9$ và loài $11$, mỗi loài gồm có $3$ con côn trùng. Lực lượng của loài côn trùng hiếm nhất là $1$. Các loài có ít con côn trùng nhất là loài $7$, loài $0$ và loài $100$, mỗi loài gồm $1$ con côn trùng.

Pak Blangkon không biết loài côn trùng nào cả. Anh ta có một chiếc máy chỉ với một nút bấm có thể cung cấp một số thông tin về các loài côn trùng. Ban đầu, máy trống rỗng. Để sử dụng máy, có thể thực hiện ba loại thao tác:

Di chuyển một con côn trùng vào trong máy.
Di chuyển một con côn trùng ra ngoài máy.
Nhấn nút trên máy.

Mỗi loại thao tác có thể được thực hiện nhiều nhất là $40 \; 000$ lần.

Bất cứ khi nào nút được nhấn, máy sẽ báo lực lượng loài côn trùng thường gặp nhất, chỉ xét các con côn trùng bên trong máy.

Nhiệm vụ của bạn là xác định lực lượng của loài côn trùng hiếm nhất trong số tất cả $N$ con côn trùng trong nhà của Pak Blangkon bằng cách sử dụng máy.
Ngoài ra, trong một số subtask, điểm của bạn phụ thuộc vào số lượng tối đa các thao tác của một loại đã sử dụng (xem phần Subtask để biết thêm chi tiết).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

C++

int min_cardinality(int N)

$N$: số lượng con côn trùng.
Hàm này cần trả về lực lượng của loài côn trùng hiếm nhất trong số tất cả $N$ con côn trùng trong nhà của Pak Blangkon.
Hàm này được gọi đúng một lần.

Hàm trên có thể thực hiện các lời gọi đến các hàm sau:

C++

void move_inside(int i)

$i$: chỉ số của con côn trùng được di chuyển vào trong máy. Giá trị của $i$ phải nằm trong khoảng từ $0$ đến $N - 1$ bao gồm cả hai đầu mút.
Nếu con côn trùng này đã ở trong máy, thì lời gọi này không ảnh hưởng đến tập các con côn trùng trong máy. Tuy nhiên, nó vẫn được tính là một lời gọi riêng biệt.
Hàm này có thể được gọi nhiều nhất là $ 40 \; 000 $ lần.

C++

void move_outside(int i)

$i$: chỉ số của con côn trùng được di chuyển ra ngoài máy. Giá trị của $i$ phải nằm trong khoảng từ $0$ đến $N - 1$ bao gồm cả hai đầu mút.
Nếu con côn trùng này đã ở bên ngoài máy, lời gọi này sẽ không ảnh hưởng đến tập các con côn trùng trong máy. Tuy nhiên, nó vẫn được tính là một lời gọi riêng biệt.
Hàm này có thể được gọi nhiều nhất là $ 40 \; 000 $ lần.

C++

int press_button()

Hàm này trả về lực lượng của loài côn trùng thường gặp nhất, chỉ xét các con côn trùng bên trong máy.
Hàm này có thể được gọi nhiều nhất là $ 40 \; 000 $ lần.
Trình chấm là không thích ứng. Nghĩa là, các loài của $N$ con côn trùng được cố định trước khi gọi min_cardinality.

Ví dụ

Xét một kịch bản trong đó có $6$ con côn trùng thuộc các loài tương ứng $[5, 8, 9, 5, 9, 9]$. Hàm min_cardinality được gọi như sau:

C++

min_cardinality(6)

Hàm có thể gọi move_inside, move_outside, và press_button như sau.

Lời gọi	Giá trị trả về	Các con côn trùng trong máy	Loài của các con côn trùng trong máy
		$\\{\\}$	$[]$
`move_inside(0)`		$\\{0\\}$	$[5]$
`press_button()`	$1$	$\\{0\\}$	$[5]$
`move_inside(1)`		$\\{0, 1\\}$	$[5, 8]$
`press_button()`	$1$	$\\{0, 1\\}$	$[5, 8]$
`move_inside(3)`		$\\{0, 1, 3\\}$	$[5, 8, 5]$
`press_button()`	$2$	$\\{0, 1, 3\\}$	$[5, 8, 5]$
`move_inside(2)`		$\\{0, 1, 2, 3\\}$	$[5, 8, 9, 5]$
`move_inside(4)`		$\\{0, 1, 2, 3, 4\\}$	$[5, 8, 9, 5, 9]$
`move_inside(5)`		$\\{0, 1, 2, 3, 4, 5\\}$	$[5, 8, 9, 5, 9, 9]$
`press_button()`	$3$	$\\{0, 1, 2, 3, 4, 5\\}$	$[5, 8, 9, 5, 9, 9]$
`move_inside(5)`		$\\{0, 1, 2, 3, 4, 5\\}$	$[5, 8, 9, 5, 9, 9]$
`press_button()`	$3$	$\\{0, 1, 2, 3, 4, 5\\}$	$[5, 8, 9, 5, 9, 9]$
`move_outside(5)`		$\\{0, 1, 2, 3, 4\\}$	$[5, 8, 9, 5, 9]$
`press_button()`	$2$	$\\{0, 1, 2, 3, 4\\}$	$[5, 8, 9, 5, 9]$

Tại thời điểm này, có đủ thông tin để kết luận rằng lực lượng của loài côn trùng hiếm nhất là $1$. Do đó, hàm min_cardinality cần trả về $1$.

Trong ví dụ này, move_inside được gọi $7$ lần, move_outside được gọi $1$ lần và press_button được gọi $6$ lần.

Ràng buộc

$2 \le N \le 2000$

Phân nhóm

(10 điểm) $N \le 200$
(15 điểm) $N \le 1000$
(75 điểm) Không có ràng buộc gì thêm.

Nếu trong bất kì trường hợp thử nghiệm nào, các lời gọi đến các hàm move_inside, move_outside hoặc press_button không tuân theo các ràng buộc được mô tả trong phần Chi tiết cài đặt hoặc giá trị trả về của min_cardinality không đúng, điểm của bạn cho subtask đó sẽ là $0$.

Gọi $q$ là giá trị lớn nhất trong ba giá trị sau: số lần gọi hàm move_inside, số lời gọi hàm move_outside và số lần gọi hàm press_button.

Trong subtask 3, bạn có thể nhận được một phần điểm. Gọi $m$ là giá trị lớn nhất của $\frac{q}{N}$ trong tất cả các trường hợp thử nghiệm của subtask này.
Điểm của bạn cho subtask này được tính theo bảng sau:

Điều kiện	Điểm
$20 < m$	$0$ (thông báo "`Output isn’t correct`" trong CMS)
$6 < m \le 20$	$\frac{225}{m - 2}$
$3 < m \le 6$	$81 - \frac{2}{3} m^2$
$m \le 3$	$75$

Trình chấm mẫu

Gọi $T$ là một mảng gồm $N$ số nguyên trong đó $T[i]$ là loài của con côn trùng $i$.

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng $1$: $N$
dòng $2$: $T[0] \; T[1] \; \ldots \; T[N - 1]$

Nếu trình chấm mẫu phát hiện được sự vi phạm giao thức, trình chấm mẫu sẽ xuất ra Protocol Violation: <MSG>, trong đó <MSG> thuộc một trong các loại sau:

invalid parameter: trong lời gọi hàm move_inside hoặc move_outside, giá trị của $i$ không thuộc đoạn $0$ và $N - 1$ bao gồm cả hai đầu mút.
too many calls: số lượng lời gọi tới một trong move_inside, move_outside, hoặc press_button vượt quá $40\;000$.

Ngược lại, trình chấm sẽ xuất ra theo khuôn dạng sau:

dòng $1$: giá trị trả về của min_cardinality
dòng $2$: $q$

Nguồn: Đề thi chính thức IOI 2022, bản tiếng Việt, giấy phép CC-BY.

3. IOI 2022 - Thousands Islands

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 2G Input: bàn phím Output: màn hình

Vạn Đảo là một nhóm những hòn đảo tuyệt đẹp nằm ở biển Java.
Có tổng cộng $N$ hòn đảo, được đánh số từ $0$ đến $N-1$.

Có $M$ ca nô, được đánh số từ $0$ đến $M-1$, được sử dụng để di chuyển giữa các hòn đảo.
Với mỗi $i$ mà $0 \le i \le M - 1$, ca nô $i$ có thể neo đậu ở đảo $U[i]$ hoặc $V[i]$, và được sử dụng để di chuyển giữa đảo $U[i]$ và $V[i]$.
Cụ thể, khi ca nô đang neo đậu ở đảo $U[i]$, nó có thể được sử dụng để di chuyển từ đảo $U[i]$ đến đảo $V[i]$, sau đó ca nô sẽ được neo đậu tại đảo $V[i]$.
Tương tự, khi ca nô đang được neo đậu ở đảo $V[i]$, nó có thể được sử dụng để di chuyển từ đảo $V[i]$ đến đảo $U[i]$, sau đó ca nô sẽ được neo đậu tại đảo $U[i]$.
Ban đầu, ca nô được neo đậu tại đảo $U[i]$.
Có thể có nhiều ca nô được sử dụng để di chuyển giữa một cặp hai hòn đảo.
Cũng có thể có nhiều ca nô cùng được neo đậu tại một hòn đảo.

Vì lý do an toàn, mỗi chiếc ca nô cần phải được bảo dưỡng sau mỗi lần nó di chuyển, điều này làm cho một chiếc ca nô không được phép di chuyển hai lần liên tiếp.
Nói cách khác, sau khi sử dụng ca nô $i$, một chiếc ca nô khác phải được sử dụng trước khi ca nô $i$ có thể được sử dụng tiếp.

Bu Dengklek muốn lên kế hoạch cho một hành trình quanh một số hòn đảo.
Một hành trình là hợp lệ khi và chỉ khi thoả mãn những điều kiện sau.

Cô ấy bắt đầu và kết thúc hành trình ở hòn đảo $0$.
Cô phải ghé thăm ít nhất một hòn đảo khác hòn đảo $0$.
Sau khi hành trình kết thúc, mỗi chiếc ca nô phải được neo đậu tại hòn đảo mà nó đã được neo đậu trước hành trình.
Có nghĩa là, ca nô $i$, với mỗi $i$ mà $0 \le i \le M - 1$, phải được neo đậu tại đảo $U[i]$.

Hãy giúp Bu Dengklek tìm ra một hành trình hợp lệ gồm nhiều nhất $2\;000\;000$ lần di chuyển, hoặc xác định rằng không có một hành trình hợp lệ nào tồn tại.
Có thể chứng minh được rằng với những ràng buộc trong bài toán này (xem phần Ràng buộc), nếu có một hành trình hợp lệ bất kỳ tồn tại, thì cũng có một hành trình hợp lệ mà không bao gồm quá $2\;000\;000$ lần di chuyển.

Chi tiết cài đặt

Bạn cần phải cài đặt hàm sau:

C++

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V);

$N$: số lượng hòn đảo.
$M$: số lượng ca nô.
$U$, $V$: các mảng gồm $M$ phần tử mô tả các ca nô.
Hàm cần trả về một biến boolean hoặc một mảng các số nguyên.
Nếu không có hành trình hợp lệ, hàm cần trả về giá trị false.
Nếu tồn tại một hành trình hợp lệ, có hai lựa chọn:
- Để nhận được điểm tuyệt đối, hàm cần trả về một mảng nhiều nhất $2\;000\;000$ số nguyên thể hiện hành trình hợp lệ đó. Cụ thể hơn, các phần tử của mảng này phải là các chỉ số của các ca nô được sử dụng trong hành trình (theo thứ tự mà chúng được sử dụng).
- Để nhận được một phần điểm, hàm cần trả về true, một mảng nhiều hơn $2\;000\;000$ số nguyên, hay một mảng số nguyên không thể hiện một hành trình hợp lệ. (Xem chi tiết ở phần Subtask).
Hàm này được gọi đúng một lần.

Ví dụ

Ví dụ 1

Xét lời gọi hàm:

C++

find_journey(4, 5, [0, 1, 2, 0, 3], [1, 2, 3, 3, 1])

Các đảo và các ca nô được mô tả ở bức ảnh sau đây.

Một hành trình hợp lệ có thể là.
Đầu tiên, Bu Dengklek lần lượt sử dụng các ca nô $0$, $1$, $2$ và $4$.
Lúc này, cô ấy ở đảo $1$.
Sau đó, Bu Dengklek có thể sử dụng ca nô $0$ một lần nữa vì lúc này nó đang được neo đậu ở đảo $1$ và ca nô trước đó mà cô ấy sử dụng không phải là ca nô $0$.
Sau khi di chuyển bằng ca nô $0$ một lần nữa, Bu Dengklek ở đảo $0$.
Tuy nhiên, ca nô $1$, $2$ và $4$ đang không được neo đậu ở hòn đảo ban đầu trước hành trình.
Bu Dengklek sau đó tiếp tục hành trình bằng cách sử dụng ca nô $3$, $2$, $1$, $4$ và $3$ một lần nữa.
Bu Dengklek bây giờ đã trở lại đảo $0$ và tất cả các ca nô đã được neo đậu ở hòn đảo ban đầu trước khi hành trình bắt đầu.

Vì vậy, kết quả trả về $[0, 1, 2, 4, 0, 3, 2, 1, 4, 3]$ thể hiện một hành trình hợp lệ.

Ví dụ 2

Xét lời gọi hàm sau:

C++

find_journey(2, 3, [0, 1, 1], [1, 0, 0])

Các đảo và các ca nô được mô tả ở bức ảnh sau đây.

Bu Dengklek chỉ có thể bắt đầu bằng việc di chuyển với ca nô $0$, sau đó cô ấy có thể di chuyển với ca nô $1$ hoặc $2$.
Lưu ý rằng cô ấy không thể di chuyển với ca nô $0$ hai lần liên tiếp.
Trong cả hai trường hợp, Bu Dengklek đều quay trở lại đảo $0$.
Tuy nhiên, các ca nô đang không được neo đậu tại hòn đảo ban đầu trước hành trình, và Bu Dengklek không thể di chuyển bằng ca nô nào tiếp theo vì ca nô duy nhất đang ở đảo $0$ là chiếc ca nô cô ấy vừa mới sử dụng.
Vì không có một hành trình hợp lệ, hàm cần trả về giá trị false.

Ràng buộc

$2 \le N \le 100\;000$
$1 \le M \le 200\;000$
$0 \le U[i] \le N - 1$ và $0 \le V[i] \le N - 1$ (với mỗi $i$ mà $0 \le i \le M - 1$)
$U[i] \neq V[i]$ (với mỗi $i$ mà $0 \le i \le M - 1$)

Phân nhóm

(5 điểm) $N = 2$
(5 điểm) $N \le 400$.
Với mỗi cặp đảo $x$ và $y$ khác nhau ($0 \le x < y \le N - 1$), có đúng hai ca nô được sử dụng để di chuyển giữa chúng.
Một ca nô được neo đậu ở đảo $x$, ca nô còn lại được neo đậu ở đảo $y$.
(21 điểm) $N \le 1000$, $M$ chẵn, với mỗi $i$ chẵn mà $0 \le i \le M - 1$, ca nô $i$ và $i + 1$ đều có thể được sử dụng để di chuyển giữa đảo $U[i]$ và đảo $V[i]$.
Ban đầu, ca nô $i$ được neo đậu tại đảo $U[i]$ còn ca nô $i + 1$ được neo đậu tại đảo $V[i]$.
Cụ thể, $U[i] = V[i + 1]$ và $V[i] = U[i + 1]$.
(24 điểm) $N \le 1000$, $M$ chẵn, với mỗi $i$ chẵn mà $0 \le i \le M - 1$, ca nô $i$ và $i + 1$ đều có thể được sử dụng để di chuyển giữa đảo $U[i]$ và đảo $V[i]$.
Ban đầu, cả hai ca nô được neo đậu tại đảo $U[i]$.
Cụ thể, $U[i] = U[i + 1]$ và $V[i] = V[i + 1]$.
(45 điểm) Không có ràng buộc nào thêm.

Với mỗi trường hợp thử nghiệm mà có tồn tại một hành trình hợp lệ, lời giải của bạn:

nhận được điểm tối đa nếu bạn trả về một hành trình hợp lệ,
nhận được $35\%$ số điểm nếu bạn trả về true, một mảng có nhiều hơn $2\;000\;000$ số nguyên, hoặc một mảng không mô tả một hành trình hợp lệ,
nhận được $0$ điểm trong các trường hợp khác.

Với mỗi trường hợp thử nghiệm mà không tồn tại một hành trình hợp lệ, lời giải của bạn:

nhận được điểm tối đa nếu bạn trả về false,
nhận được $0$ điểm trong các trường hợp khác.

Lưu ý rằng điểm cho mỗi subtask là số điểm nhỏ nhất của các trường hợp thử nghiệm trong subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

dòng $1$: $N \; M$
dòng $2 + i$ ($0 \le i \le M - 1$): $U[i] \; V[i]$

Trình chấm mẫu in kết quả của bạn theo định dạng sau:

Nếu hàm find_journey trả về một biến kiểu bool:
dòng $1$: $0$
dòng $2$: $0$ nếu hàm find_journey trả về false, hay $1$ nếu ngược lại.
Nếu hàm find_journey trả về một std::vector<int>, gọi các phần tử của mảng này là $c[0], c[1], \ldots,c[k-1]$. Trình chấm mẫu sẽ in ra:
dòng $1$: $1$
dòng $2$: $k$
dòng $3$: $c[0] \; c[1] \; \ldots \; c[k-1]$

Nguồn: Đề thi chính thức IOI 2022, bản tiếng Việt, giấy phép CC-BY.

Lời gọi	Giá trị trả về	Các con côn trùng trong máy	Loài của các con côn trùng trong máy
		\(\\{\\}\)	\([]\)
`move_inside(0)`		\(\\{0\\}\)	\([5]\)
`press_button()`	\(1\)	\(\\{0\\}\)	\([5]\)
`move_inside(1)`		\(\\{0, 1\\}\)	\([5, 8]\)
`press_button()`	\(1\)	\(\\{0, 1\\}\)	\([5, 8]\)
`move_inside(3)`		\(\\{0, 1, 3\\}\)	\([5, 8, 5]\)
`press_button()`	\(2\)	\(\\{0, 1, 3\\}\)	\([5, 8, 5]\)
`move_inside(2)`		\(\\{0, 1, 2, 3\\}\)	\([5, 8, 9, 5]\)
`move_inside(4)`		\(\\{0, 1, 2, 3, 4\\}\)	\([5, 8, 9, 5, 9]\)
`move_inside(5)`		\(\\{0, 1, 2, 3, 4, 5\\}\)	\([5, 8, 9, 5, 9, 9]\)
`press_button()`	\(3\)	\(\\{0, 1, 2, 3, 4, 5\\}\)	\([5, 8, 9, 5, 9, 9]\)
`move_inside(5)`		\(\\{0, 1, 2, 3, 4, 5\\}\)	\([5, 8, 9, 5, 9, 9]\)
`press_button()`	\(3\)	\(\\{0, 1, 2, 3, 4, 5\\}\)	\([5, 8, 9, 5, 9, 9]\)
`move_outside(5)`		\(\\{0, 1, 2, 3, 4\\}\)	\([5, 8, 9, 5, 9]\)
`press_button()`	\(2\)	\(\\{0, 1, 2, 3, 4\\}\)	\([5, 8, 9, 5, 9]\)

Điều kiện	Điểm
\(20 < m\)	\(0\) (thông báo "`Output isn’t correct`" trong CMS)
\(6 < m \le 20\)	\(\frac{225}{m - 2}\)
\(3 < m \le 6\)	\(81 - \frac{2}{3} m^2\)
\(m \le 3\)	\(75\)