#1559. SOCIAL - Giãn cách xã hội

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Contest PVH 2021 - 2022

Trong hoàn cảnh dịch bệnh COVID-19 diễn biến phức tạp và trước biến thể Delta lây lan nhanh đe dọa hệ thống y tế, việc áp dụng giãn cách xã hội là biện pháp hiệu quả để ngăn chặn sự gia tăng số ca nhiễm, thông qua việc hạn chế tiếp xúc giữa người với người. Tuy nhiên, áp dụng giãn cách xã hội để lại nhiều hệ lụy về kinh tế và đời sống của người dân như đứt gẫy chuỗi cung ứng hàng hóa thiết yếu, gia tăng số người mất việc làm hay làm gián đoạn nhiều hoạt động khác. Vì vậy, quyết định có áp dụng giãn cách xã hội hay không đòi hỏi sự cân nhắc về nhiều mặt như tính cấp thiết và tác động lâu dài.

Quốc gia X có n thành phố, các thành phố được đánh số từ 1 tới n . Mạng lưới giao thông đường bộ của quốc gia này gồm m con đường hai chiều được đánh số từ 1 đến m , con đường thứ j nối thành phố u_j với thành phố v_j . Nhằm xây dựng các kịch bản ứng phó khi dịch COVID-19 bùng phát trong cộng đồng, chính phủ quốc gia X tiến hành đánh giá mức độ cản trở giao thông nếu một thành phố hoặc một con đường bị phong tỏa. Cụ thể, mức độ cản trở giao thông khi phong tỏa con đường thứ j là số cặp thánh phố (x, y) không thể đi được tới nhau nếu chỉ riêng con đường thứ j bị xóa khỏi mạng lưới giao thông. Tương tự, mức độ cản trở giao thông khi phong tỏa thành phố thứ i là số cặp thành phố (x, y) (với x \cdot y + i^2 \neq (x + y) \cdot i ) không thể đi được tới nhau nếu chỉ riêng thành phố thứ i bị xóa khỏi mạng lưới giao thông. Chú ý rằng, khi một thành phố bị phong tỏa, các con đường nối trực tiếp với thành phố này cũng bị phong tỏa theo.

Các bạn hãy giúp chính phủ quốc gia X tính mức độ cản trở giao thông khi phong tỏa của mỗi thành phố và mỗi con đường nhé.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên \theta (1 \leq \theta \leq 4) là số thứ tự của subtask chứa test này;
  • Dòng thứ hai chứa hai số nguyên n m (1 \leq n \leq 3 \cdot 10^5, n - 1 \leq m \leq 3 \cdot 10^5) lần lượt là số thành phố và số con đường ở quốc gia X;
  • Trong m dòng còn lại, dòng thứ j chứa hai số nguyên u_j v_j (1 \leq u_j, v_j \leq n) mô tả con đường thứ j .

Dữ liệu ra:

In ra hai dòng:

  • Dòng đầu tiên chứa n số nguyên, trong đó số thứ i là mức độ cản trở giao thông khi phong tỏa thành phố thứ i .
  • Dòng thứ hai chứa m số nguyên, trong đó số thứ j là mức độ cản trở giao thông khi phong tỏa con đường thứ j .

Do các kết quả có thể rất lớn, các bạn chỉ ghi ra phần dư của n + m giá trị trên khi chia cho 998244353 .

Ví dụ:

Dữ liệu vào:

1
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

Dữ liệu ra:

0 0 6 6 0 0
0 0 0 9 0 0 0

Giải thích:

Hình vẽ dưới đây mô tả mạng lưới giao thông trong ví dụ ở trên:

  • Nếu thành phố 1 bị phong tỏa, các con đường nối từ đây tới thành phố 2 3 cũng bị phong tỏa theo. Tuy nhiên, 5 thành phố còn lại vẫn có thể đi được tới nhau thông qua những con đường khác. Vì vậy mức độ cản trở giao thông khi phong tỏa thành phố 1 0 . Tương tự với các thành phố 2 , 5 6 .
  • Nếu thành phố 3 bị phong tỏa, 6 cặp thành phố sau sẽ không thể tới được nhau: (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6) .
  • Nếu con đường nối hai thành phố 3 4 bị phong tỏa, 9 cặp thành phố sau sẽ không thể tới được nhau: (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6) .
  • Ngoại trừ con đường kể trên, việc phong tỏa chỉ một con đường nào khác đều không ảnh hưởng tới việc đi lại giữa cả 6 thành phố. Do đó, mức độ cản trở giao thông khi phong tỏa các con đường này là 0 .

Giới hạn:

Bộ test của bài được chia làm các subtask như sau:

  • Subtask 1 ( \frac{13}{70} số điểm): n \leq 300 m \leq 300 ;
  • Subtask 2 ( \frac{17}{70} số điểm khác): n \leq 3000 m \leq 3000 ;
  • Subtask 3 ( \frac{17}{70} số điểm khác): Mạng lưới giao thông có dạng cây. Nói cách khác, m = n - 1 và các con đường không tạo thành chu trình;
  • Subtask 4 ( \frac{23}{70} số điểm còn lại): Không có ràng buộc gì thêm.