Seems like this should do this:
^[a-zA-Z0-9][-a-zA-Z0-9]{0,61}[a-zA-Z0-9]$
Matches any alphanumeric character, and then matches 61 alphanumeric characters (including hyphens), and then matches any alphanumeric character. The minimum line length is 2, the maximum is 63. It does not work with Unicode. If you need to work with Unicode, you need to add different character classes instead of a-zA-Z0-9 , but the principle will be the same.
I believe that the correct grep expression will work with Unicode:
^[[:alnum:]][-[:alnum:]]{0,61}[[:alnum:]]$
Welbog
source share