Nguyên Liệu Chung Lễ Hội Đền Trần

Mô tả

Lễ hội đền Trần năm nay quy tụ rất nhiều bếp đoàn về nấu cỗ tế tổ. Mỗi bếp đoàn mang theo một danh sách các loại nguyên liệu (mỗi loại được biểu diễn bằng một mã số nguyên dương). Ban tổ chức muốn tìm ra những nguyên liệu chung — tức là loại nguyên liệu xuất hiện trong danh sách của tất cả các bếp đoàn — để thống nhất nguồn cung cấp sỉ.

Bạn được cho danh sách tổng hợp gồm m phần tử, trong đó mỗi phần tử là một cặp (mã_nguyên_liệu, mã_bếp_đoàn). Nhiệm vụ của bạn là đếm xem có bao nhiêu mã nguyên liệu khác nhau xuất hiện ở mọi bếp đoàn từ 1 đến n.

Lưu ý: một bếp đoàn có thể báo cùng một nguyên liệu nhiều lần, nhưng bạn chỉ cần biết nguyên liệu đó có xuất hiện ít nhất một lần ở bếp đoàn ấy hay không.

Đầu vào

• Số nguyên n (số bếp đoàn, đánh số từ 1 đến n).
• Số nguyên m (số bản ghi trong danh sách tổng hợp).
• Mảng records gồm m phần tử, mỗi phần tử là một mảng hai số nguyên [ingredient_id, team_id].

Đầu ra

• Trả về một số nguyên duy nhất: số lượng nguyên liệu xuất hiện ở tất cả n bếp đoàn.

Ràng buộc

• 1 ≤ n ≤ 10^5
• 0 ≤ m ≤ 2·10^5
• 1 ≤ ingredient_id ≤ 10^9
• 1 ≤ team_id ≤ n
• Mọi giá trị trung gian đều nằm trong khoảng an toàn của số nguyên 64-bit.

Ví dụ

Ví dụ 1

n = 3, m = 8 records = [[10,1],[10,2],[10,3],[20,1],[20,2],[30,2],[30,3],[40,3]]

Giải thích từng bước:

• Nguyên liệu 10: xuất hiện ở đoàn 1, 2, 3 → đủ cả 3 đoàn.
• Nguyên liệu 20: xuất hiện ở đoàn 1, 2 → thiếu đoàn 3.
• Nguyên liệu 30: xuất hiện ở đoàn 2, 3 → thiếu đoàn 1.
• Nguyên liệu 40: chỉ có ở đoàn 3.

Chỉ có nguyên liệu 10 là xuất hiện ở tất cả các đoàn, vậy kết quả là 1.

Ví dụ 2

n = 2, m = 4 records = [[5,1],[5,2],[7,1],[7,2]]

Cả nguyên liệu 5 và 7 đều xuất hiện ở đoàn 1 và đoàn 2, nên đáp án là 2.