Error ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)?

Question

MySQL

Good afternoon. Please explain why this is happening!
Is VDS it is necessary to deliver php nginx mysql Everything except mysql works well.
In general, install MYSQL

sudo apt update
sudo apt install mysql-server
sudo mysql_secure_installation

This thing helped me set up mysql_secure_installation.
In general, after setting I type

sudo mysql

Everything is good! Earned! Logged in.
Also works in the following ways

sudo mysql -u root -p

Dumps are poured all OK!
AND THIS IS WHAT I DO

service mysql restart

And all pi ... ets!

ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: NO)
ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)

I can not log in via root, even with a password, even without! Only if I reinstall with a complete removal.
The config did not change! I don't touch anything at all.
Who is smarter, help!