// viet de thoi, ac roi thi khong can lam dau :>

Cho ~G~ là một đồ thị có hướng không có chu trình, các đỉnh được đánh số từ ~1~. Có một đồng xu màu trắng đặt ở đỉnh ~w~ và một đồng xu màu đen đặt ở đỉnh ~b~. Hai người chơi một trò chơi trên ~G~ như sau:

• Hai người chơi luân phiên nhau thực hiện lượt chơi.
• Đến lượt mình, người chơi chọn một đồng xu bất kỳ và di chuyển nó. Nếu đồng xu màu trắng thì phải di chuyển theo các cung của đồ thị. Nếu đồng xu màu đen thì phải di chuyển ngược các cung của đồ thị. Tức là có thể di chuyển đồng xu màu trắng từ ~x~ sang ~y~ nếu ~(x, y)~ là một cung của đồ thị, và có thể di chuyển đồng xu màu đen từ ~u~ sang ~v~ nếu ~(v, u)~ là một cung của đồ thị.
• Ai không thực hiện được lượt chơi hợp lệ nữa sẽ thua cuộc. Rõ ràng là trò chơi sẽ kết thúc sau hữu hạn bước, nên sẽ không có kết quả hòa.
• Nếu người chơi biết mình sẽ thắng, anh ta sẽ cố gắng thắng nhanh nhất có thể (cực tiểu hóa số lượt chơi).
• Nếu người chơi biết mình sẽ thua, anh ta sẽ cố gắng kéo dài thời gian (cực đại hóa số lượt chơi)

Biết rằng hai người chơi đều rất thông minh, hãy xác định số lượt chơi sẽ được thực hiện trong trò chơi.

Input

• Dòng đầu tiên chứa ~n~, ~m~, ~w~, ~b~ (~1 \leq n, m \leq 5000~, ~1 \leq w, b \leq n~) là số đỉnh, số cung, vị trí của đồng xu màu trắng, vị trí của đồng xu màu đen.
• ~m~ dòng tiếp theo mỗi dòng chứa một cung ~u~, ~v~ (~1 \leq u, v \leq n~).

Output

• Ghi một số nguyên là số lượt chơi sẽ được thực hiện.

Scoring

• Subtask 1 (~50\%~ số điểm): Đỉnh ~b~ không có cung đi vào.
• Subtask 2 (~50\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

9 11 3 3 
1 2
2 3 
3 4 
4 5 
5 6 
1 3 
3 6 
1 7 
7 8 
8 9 
9 3

Sample Output 1

 5

Có một trò chơi như sau:

• Có ~n~ viên bi
• Mỗi lượt chơi, người chơi lấy đi ba hoặc năm hoặc bảy hoặc chín viên bi (tất nhiên là nếu có đủ bi)
• Hai người luân phiên nhau thực hiện lượt chơi. Ai không thực hiện được lượt chơi nữa (tức số bi còn lại bé hơn ba) thì thua cuộc

Xác định ai là người chiến thắng, biết rằng cả hai đều chơi tối ưu.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ là số lượng testcase ~(1 \le T \le 10^5)~
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ ~(1 \le n \le 10^{18})~

Output

• Ghi ra ~T~ dòng, mỗi dòng ghi ~1/2~ tương ứng là người đi trước / sau thắng.

Sample Input

4
11
12
13
100

Sample Output

1
2
2
1

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi ít nhất một và nhiều nhất là tất cả số sỏi trong đống đó. Người không thể thực hiện được lượt đi hợp lệ (tức là khi tất cả các đống đều rỗng) sẽ thua cuộc.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ - số lượng đống sỏi ( ~1 \le N \le 10^5~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^9~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Sample Input 1

3
1 4 5

Sample Output 1

2

Sample Input 2

3
1 4 6

Sample Output 2

1

Có ~n~ đống sỏi, đống thứ i ban đầu có ~a_i~ viên sỏi.
Hai người chơi: bạn và Jury sẽ lần lượt thực hiện các lượt đi.

• Ở mỗi lượt, người chơi chọn một đống còn sỏi và lấy đi ít nhất 1 viên sỏi (và không nhiều hơn số sỏi hiện có trong đống đó).
• Người không thể thực hiện lượt đi hợp lệ (tức là tất cả các đống đều rỗng) sẽ thua.

Ban đầu bạn là người đi trước.
Jury sẽ chơi tối ưu, và bạn cần cố gắng chiến thắng trò chơi. Biết rằng input được sinh ra để bạn luôn có thể làm điều đó nếu chơi tối ưu.

Cách Thức Giao Tiếp

• Khi chương trình của bạn bắt đầu, Jury sẽ gửi cho bạn hai dòng đầu tiên:

  • Dòng 1: số nguyên ~n~ – số đống sỏi.
  • Dòng 2: chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ – số sỏi ban đầu trong mỗi đống.

• Sau đó, các lượt chơi diễn ra luân phiên như sau:

• Trò chơi kết thúc khi tất cả các đống đều rỗng.

Luật hợp lệ

• Mọi nước đi phải thoả mãn:
  • 1 ≤ x ≤ n
  • 1 ≤ y ≤ a[x] (trước khi lấy)
• Nếu bạn in ra giá trị không hợp lệ, chương trình sẽ bị dừng (TLE / Runtime Error).

Nhiệm vụ của bạn

Viết chương trình tương tác để chơi và chiến thắng trò chơi Nim với chiến lược tối ưu.

Giới hạn

• ~1 \leq n \leq 50~
• ~1 \leq a_i \leq 100~
• Số lượt tối đa: ~3 \times 10^5~

Ví dụ Minh Họa

Giả sử Jury có đầu vào:

3
1 2 3

Diễn tiến

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi ít nhất một và nhiều nhất là tất cả số sỏi trong đống đó. Người không thể thực hiện được lượt đi hợp lệ (tức là khi tất cả các đống đều rỗng) sẽ thua cuộc.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng.

Tuy nhiên, điểm đặc biệt ở phiên bản này, là bạn sẽ có một đống sỏi phụ ở bên ngoài. Đống sỏi này có ~M~ viên sỏi và sẽ không tính vào ~n~ đống sỏi của trò chơi. Ở mỗi lượt, bạn được thêm một lựa chọn, đó là lấy một lượng ~1 \le x \le M~ viên sỏi còn lại trong đống đó, rồi thêm các viên sỏi đó vào một đống sỏi tuỳ ý nào đó trong ~n~ đống sỏi.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, đồng thời tham số ~M~ là số viên sỏi của đống phụ, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, M~ - số lượng đống sỏi ( ~1 \le N \le 10^5; 1 \le M \le 10^9~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^9~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Sample Input 2

3 6
1 4 6

Sample Output 2

1

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi ~1 \le x~ viên sỏi thuộc đống đó. Tuy nhiên đây là phiên bản khó, nên mỗi đống sỏi bạn sẽ chỉ được lấy tối đa ~B_i~ viên mà thôi. Người không thể thực hiện được lượt đi hợp lệ (tức là khi tất cả các đống đều rỗng) sẽ thua cuộc.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ - số lượng đống sỏi ( ~1 \le N \le 10^5~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^9~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~B_1, B_2, \dots, B_N~ ( ~1 \le A_i \le 10^9~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Const:

• Có ~25\%~ số test có ~N = 1~.

Sample Input 1

1
28
6

Sample Output 1

2

Sample Input 2

2
8 18
3 5

Sample Output 2

2

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi một số viên sỏi ở đó thoả mãn:

• Gọi ~x~ là số viên sỏi ở đống sỏi mà người chơi chọn. Gọi ~y~ là số viên sỏi mà người chơi sẽ lấy ra, ~y~ phải là một số nguyên dương thoả mãn ~gcd(x,y) = 1~.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng, biết rằng nếu đến lượt ai mà người đó không thể thực hiện lượt chơi thì sẽ thua.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ - số lượng đống sỏi ( ~1 \le N \le 10^5~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^7~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Sample Input 1

4
3 3 6 1

Sample Output 1

1

Sample Input 2

5
1 2 3 4 5

Sample Output 2

2

Cho ~G~ là một đồ thị có hướng không có chu trình, các đỉnh được đánh số từ 1 đến ~n~. Tại đỉnh thứ ~i~ có một số nguyên dương ~a_i~. An và Bình chơi một trò chơi như sau:

• Hai người chơi luân phiên nhau thực hiện lượt chơi, An đi trước
• Đến lượt mình, người chơi chọn một đỉnh ~i~ tùy ý, sau đó anh ta chia ~a_i~ cho một ước tùy ý (lớn hơn 1) của ~a_i~, sau đó với mỗi đỉnh ~j~ kề với ~i~ anh ta có thể giảm ~a_j~ đi một lượng là số nguyên dương khác không tùy ý (các đỉnh khác nhau có thể giam một lượng khác nhau).
• Ai không thực hiện được lượt chơi hợp lệ nữa sẽ thua cuộc. Rõ ràng là trò chơi sẽ kết thúc sau hữu hạn bước, nên sẽ không có kết quả hòa. Biết rằng hai người chơi đều rất thông minh, hãy xác định ai là người chiến thắng

Input

Dòng đầu tiên chứa ~T~ là số lượng testcase, với mỗi testcase:

• Dòng đầu tiên chứa ~n~ ~m~: số đỉnh và số cung của đồ thị
• Dòng tiếp theo chứa ~a_1~ ~a_2~ ~\ldots~ ~a_n~
• ~m~ dòng tiếp theo mỗi dòng chứa một cung: ~u~ ~v~

Output

• Với mỗi testcase, ghi ra trên một dòng 1/0 tương ứng là An/Bình chiến thắng

Scoring

• Trong tất cả các test: Tổng ~n~ và tổng ~m~ trong ~T~ testcase đều không quá ~10^5~, ~1\leq a_i \leq 10^9~
• Subtask ~1~ (~10\%~ số điểm): ~m=0~ và ~a_i \leq 10^5~
• Subtask ~2~ (~20\%~ số điểm): ~m=0~
• Subtask ~3~ (~30\%~ số điểm): ~a_i \leq 10^5~
• Subtask ~4~ (~40\%~ số điểm): không ràng buộc gì thêm

Example

Sample Input 1

2 
3 0
2 8 9
9 11
2 3 4 5 6 7 8 9 1
1 2
2 3
3 4
4 5
5 6
1 3
3 6
1 7
7 8
8 9
9 3 

Sample Output 1

0
1 

Các bạn đọc đề ở link sau:

https://oj.vnoi.info/problem/voi22_matrix

Bài này chúng ta không quan trọng việc code mà sẽ đi chứng minh tại sao công thức đúng và cách tiếp cận các dạng bài tương tự.

Đây là bài giới thiệu cơ bản về dạng 2-Steps (Communication).

Hãy tưởng tượng có hai người A và B. Bạn là ban giám khảo, có một số nguyên dương ~n~, và bạn sẽ gửi số này cho người A. Người A và B cần hợp tác làm sao để B biết được số đó.

Khi nhận được số ~n~ từ bạn, người A chỉ có thể gửi thông tin cho người B bằng một xâu nhị phân với độ dài <= 40.

Khi nhận được xâu nhị phân, người B sẽ phải từ đó suy ra số ~n~ ban đầu và trả về số đó.

Các thao tác sẽ được thực hiện như trong đoạn code dưới đây:

#include <iostream>
#include <string>

using namespace std;

namespace A {
    string encode(int n) {
        // your code goes here;
    }
}

namespace B {
    int decode(string s) {
        // your code goes here
    }
}

namespace jury {
    const int Length = 40;
    bool check_valid(string &s) {
        for (char &c : s) {
            if (c != '0' && c != '1') return false;
        }

        return s.size() <= Length;
    }

    int solve() {
        int n; cin >> n;
        string val = A::encode(n);
        cout << n << ' ' << val << endl;
        if (!check_valid(val)) {
            return false;
        }
        return B::decode(val) == n;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << jury::solve(); // 1 if True, otherwise False
}

Nhiệm vụ của bạn là hoàn thiện hai hàm A::encode (nén mã) và B::decode (giải mã).

Lưu ý rằng hãy nộp thẳng tất cả code. Vì đây chỉ là bài để giới thiệu nên grader được đưa thẳng, đi thi thì chúng ta sẽ biết rằng luồng chạy của Encode và Decode là khác hẳn nhau, sẽ không biết các biến của nhau!

Sample Input

Giả sử bạn cho ~A~ giá trị ~n = 3~.

~A~ encode ~n~ thành string 111

~B~ nhận string 111 và hiểu ý của ~A~, trả về ~3~.

https://oj.uz/problem/view/IOI17_coins

https://oj.uz/problem/view/IOI19_transfer

https://oj.vnoi.info/problem/olp_sc20_attack

https://oj.uz/problem/view/JOI21_ancient_machine

Cho một đa giác lồi có ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~. Người ta chia đa giác này thành ~m+1~ đa giác con bằng ~m~ đường chéo (~m \le n-3~). Các đường chéo này cùng với ~n~ cạnh của đa giác đôi một không trùng nhau hay cắt nhau (chỉ có điểm chung tại các đầu mút). Một đa giác con gồm các đỉnh lần lượt ~x_1,x_2,...,x_t~ được coi là có giá trị ~\Sigma_{i=1}^t 2^{x_i}~.

Cho đa giác, ~m~ đường chéo và số nguyên dương ~k~ (~k \le m+1~), sắp xếp các đa giác con theo giá trị tăng dần, hãy xác định đa giác con thứ ~k~.

https://pastebin.com/WY1XGjyN

Input

• Dòng đầu gồm ba số nguyên ~n,m,k~ (~3 \le n \le 5 \times 10^5, 0 \le m \le n-3, 1 \le k \le m+1~).
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u,v~ (~1 \le u,v \le n~) thể hiện một đường chéo trong đa giác.

Output

• Một dòng chứa các đỉnh của đa giác con thứ ~k~ (các đỉnh được ghi theo thứ tự tăng dần).

Scoring

• Subtask ~1~ (~25\%~ số điểm): ~n \le 50, m \le 20~.
• Subtask ~2~ (~25\%~ số điểm): ~m = 1~.
• Subtask ~3~ (~25\%~ số điểm): ~m = n-3~.
• Subtask ~4~ (~25\%~ số điểm): không có ràng buộc gì thêm.

Example

Sample Input

6 3 2
1 3
1 4
1 5

Sample Output

1 3 4

Bài Toán Giao Tiếp (Interactive Problem)

Cửa hàng TINAMS gồm ~n~ món đồ, món đồ thứ ~i~ có giá ~p_i~. Các món đồ đều có giá đôi một phân biệt với nhau.

Bạn đã đỗ đội tuyển và muốn mua toàn bộ các món đồ trong cửa hàng. Chủ cửa hàng nhận ra bạn là một khách VIP nên đưa cho bạn một voucher khuyến mãi như sau: bạn sẽ được miễn phí ~k~ món đồ, và phải trả tiền cho ~n- k~ món đồ còn lại. Tuy nhiên, điều thú vị ở đây là, bạn sẽ không biết giá trị của các món đồ, mà chỉ biết về các tham số ~n~ và ~k~ tương đương với số lượng món đồ và số món đồ được miễn phí.

Bạn muốn tối ưu hoa lợi ích của mình, nên muốn chọn các món đồ sao cho tổng số tiền các món đồ bạn phải trả là ít nhất có thể.

Tất nhiên, bạn sẽ được hỏi ông chủ những câu có dạng như sau, bạn được quyền chọn hai số ~x~ và ~y~:

• ~?~ ~x~ ~y~ trong đó ~1\le x,y\le n~.
• Sau mỗi truy vấn bạn dùng ~endl~ để ngắt câu hỏi.
• Máy chấm sẽ đọc truy vấn và in về một số nguyên:
  • Nếu ~p[x] < p[y]~, in về y.
  • Ngược lại (khi ~p[x] > p[y]~), in về x.

Bạn không được trực tiếp đọc hay in giá trị của ~p[i]~ - chỉ so sánh thông qua các truy vấn trên.

Ở bài toán này, điểm số ở từng test của bạn sẽ được chấm bằng một hàm bí mật, chỉ biết rằng, gọi ~C_u~ là số thao tác mà bạn sử dụng, ~C_j~ là số thao tác mà giám khảo sử dụng:

• Nếu ~C_u \le C_j~ bạn sẽ được toàn bộ số điểm của test đó.
• Ngược lại, số điểm mà bạn nhận được sẽ được tính toán sao cho nếu ~C_u - C_j~ càng nhỏ, điểm số càng cao.

Input

1. Khởi đầu: Máy chấm sẽ in lên dòng đầu:

2. ~n~ ~k~ với ~1 \le n \le 10^3~ và ~1 \le k \le n~.

3. Truy vấn: Mỗi lượt bạn in:

4. ~?~ ~x~ ~y~ rồi flush. Máy chấm sẽ phản hồi x hoặc y theo mô tả ở trên.
   Bạn không được dùng quá ~10^6~ truy vấn trong toàn bộ quá trình.

5. Kết thúc: Khi đã xác định được ~k~ vị trí, bạn in:

6. ~!~ ~1~ ~1~ rồi flush.

• Dòng tiếp theo, in ra ~k~ số ~id_1, id_2, ..., id_k~ đôi một phân biệt là các món đồ mà bạn chọn để miễn phí.

Ví dụ minh hoạ

Giả sử các món đồ có giá ẩn là ~p=[2,\,5,\,1,\,4,\,3]~, ~n=5~, và ~k=2~.
Máy chấm in:

• ~5~ ~2~ Bạn có thể thực hiện:

? 1 3 → 3 (vì p[1]=2 > p[3]=1 trả về 3)
? 3 5 → 3 (1 < 3 trả về 3)
? 4 2 → 4 (4 < 5 trả về 4)
? 1 4 → 1 (2 < 4 trả về 1)
! 1 1
2 4

Trong ví dụ này, bạn báo rằng món đồ ~2~ và ~4~ là hai món đồ bạn chọn để miễn phí. Đây là một lựa chọn chính xác.

Lưu ý

• Mỗi truy vấn in đúng cú pháp ? x y rồi endl.
• Tổng số truy vấn không vượt quá ~10^6~.
• Khi hoàn thành, in ! 1 1 rồi dòng chứa đáp án.
• Đáp án bị coi là sai nếu dùng quá nhiều truy vấn hoặc in sai định dạng.

Một lớp học nhảy có ~n~ học viên nam và ~n~ học viên nữ. Cho ~m~ thông tin về các cặp học viên, thông tin thứ ~k~ ~(1 \le k \le m)~ cho biết học viên nam thứ ~i_k~ ~(1 \le i_k \le n)~ có thể nhảy cặp với học viên nữ thứ ~j_k~ ~(1 \le j_k \le n)~ .

Trong một buổi học, sau khi hướng dẫn cho tất cả các học viên, thầy giáo muốn chọn ra hai đôi nhảy, mỗi đôi gồm hai học viên (một nam và một nữ) để trình diễn và rút kinh nghiệm. Trong quá trình biểu diễn, hai cặp này sẽ đổi bạn nhảy cho nhau, do đó, thầy giáo muốn lựa chọn ra hai đôi nhảy mà khi đổi bạn nhảy, hai học viên ở đôi nhảy mới vẫn có thể nhảy cặp với nhau.

Yêu cầu: Cho ~m~ thông tin về các cặp học viên, hãy đếm số cách chọn hai cặp nhảy thỏa mãn. Hai cặp nhảy được gọi khác nhau nếu tồn tại một người thuộc vào hai cặp nhảy này nhưng không thuộc hai cặp nhảy kia.

Input

• Dòng đầu chứa hai số nguyên dương ~ n,m~ ~(m \le n^2)~
• Dòng thứ ~k~ ~(1 \le k \le m)~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~i_k, j_k~ ~(1 \le i_k , j_k \le n)~ mô tả thông tin về cặp học viên thứ ~k~.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là số cách chọn hai cặp nhảy thỏa mãn.

Subtask

• ~20\%~ số test: ~n \le 50~
• ~20\%~ số test khác : ~n \leq 300~.
• ~20\%~ số test khác : ~n \leq 10^3, m \le 2 \times 10^4~.
• ~20\%~ số test khác : ~n \leq 5 \times 10^3, m \le 2 \times 10^4~.
• ~20\%~ số test còn lại : ~n,m \leq 10^5~.

Example

Input 1

3 7
1 1
1 2
2 1
2 2
2 3
3 2
3 3

Output 1

2

Explanation