Định hướng cạnh

Cho một đồ thị gồm $n$ đỉnh và $m$ cạnh. Mỗi cạnh có thể là cạnh có hướng hoặc cạnh vô hướng. Giữa một cặp đỉnh có thể có nhiều cạnh.

Cho trước một đỉnh $s$. Bạn cần lập hai phương án định hướng:

1. Định hướng mỗi cạnh vô hướng theo một trong hai chiều sao cho số đỉnh đến được từ $s$ là lớn nhất.
2. Định hướng mỗi cạnh vô hướng theo một trong hai chiều sao cho số đỉnh đến được từ $s$ là nhỏ nhất.

Trong cả hai phương án, mọi cạnh vô hướng đều phải được định hướng. Một cạnh có thể được định hướng khác nhau ở hai phương án. Đỉnh $s$ luôn được tính là đến được từ chính nó.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $s$ — số đỉnh, số cạnh và đỉnh xuất phát.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $t_i$, $u_i$, $v_i$. Nếu $t_i=1$ thì cạnh là cạnh có hướng đi từ $u_i$ đến $v_i$. Nếu $t_i=2$ thì cạnh là cạnh vô hướng nối $u_i$ và $v_i$.

Dữ liệu đảm bảo có ít nhất một cạnh vô hướng.

Dữ liệu ra

Hai dòng đầu mô tả phương án làm cực đại số đỉnh đến được, hai dòng sau mô tả phương án làm cực tiểu.

Mỗi phương án gồm:

• Một dòng chứa số đỉnh đến được từ $s$ theo phương án đó.
• Một dòng chứa $f$ ký tự '+' hoặc '-', với $f$ là số cạnh vô hướng của đồ thị ban đầu. Ký tự thứ $j$ là '+' nếu cạnh vô hướng thứ $j$, giả sử là $(u,v)$, được định hướng từ $u$ sang $v$, và là '-' nếu định hướng ngược lại. Các cạnh vô hướng được đánh số theo đúng thứ tự xuất hiện trong dữ liệu vào.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $2\le n\le 3·{10}^5$
• $1\le m\le 3·{10}^5$
• $1\le s\le n$
• $1\le t_i\le 2$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$

Ví dụ