Network Experiment

There are n computers labeled from 1 to n. Initially, every computer is isolated. You can connect two computers with a cable; once connected, the two computers become adjacent and can communicate directly. Occasionally, a network test is performed: a message is sent from a specified computer and then propagated to all adjacent computers. Each computer that is directly or indirectly connected to the source receives the message. Note that each computer stores a particular message only once, even if it receives it from multiple paths.

Given a sequence of connection and test events, your task is to calculate the total number of messages stored in each computer.

Broadcast Process:

When a test event is issued at node x, the message is instantly broadcast to all nodes in the connected component containing x at that moment. Every affected node increments its stored message count by 1.

The events are executed in sequence and the network connections persist (i.e. they never disappear).

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), representing the number of computers and the number of events, respectively.

Each of the following m lines contains an event in one of the following two formats:

• C u v: Connect computer u and computer v with a cable (1 ≤ u, v ≤ n).
• T x: Perform a test starting from computer x (1 ≤ x ≤ n).

outputFormat

Output a single line with n integers. The i-th integer represents the total number of messages stored in computer i after processing all events.

sample

4 4
C 1 2
T 1
C 2 3
T 3

2 2 1 0