Bạn gợi ý

Trong một mạng xã hội, quan hệ bạn bè được cho dưới dạng $m$ cặp tên người dùng $(a_i,b_i)$ — nghĩa là $a_i$ và $b_i$ là bạn của nhau (quan hệ đối xứng).

Một người dùng $y$ được gọi là bạn gợi ý cho người dùng $x$ nếu thỏa mãn các điều kiện sau:

1. $x\ne y$;
2. $x$ và $y$ không phải là bạn của nhau;
3. Trong số tất cả những người dùng thỏa mãn hai điều kiện trên, $y$ có nhiều bạn chung với $x$ nhất.

Người dùng $z$ là bạn chung của $x$ và $y$ (với $z\ne x$, $z\ne y$) nếu $z$ là bạn của $x$ và đồng thời cũng là bạn của $y$.

Với mỗi người dùng trong mạng, hãy đếm số lượng bạn gợi ý của họ.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $m$ — số cặp bạn bè trong mạng.
• $m$ dòng tiếp theo, mỗi dòng chứa hai tên cách nhau bởi dấu cách: $a_i$ và $b_i$ ($a_i\ne b_i$). Tên người dùng là chuỗi khác rỗng, gồm tối đa $20$ ký tự chữ cái La-tinh in hoa hoặc in thường.

Mỗi cặp bạn bè xuất hiện đúng một lần trong dữ liệu vào (sẽ không có đồng thời cả $(x,y)$ và $(y,x)$). Các tên người dùng phân biệt là khác nhau. Mỗi người dùng có ít nhất một người bạn, do đó mỗi tên xuất hiện ít nhất một lần trong dữ liệu vào.

Dữ liệu ra

• Dòng đầu tiên in ra số người dùng $n$ trong mạng.
• $n$ dòng tiếp theo, mỗi dòng in tên một người dùng $c_i$ và số lượng bạn gợi ý $d_i$ của họ, cách nhau bởi dấu cách.

Có thể in các người dùng theo thứ tự bất kỳ.

Ràng buộc

• $1\le m\le 5000$.

Ví dụ